# Problem 9: Find the Minimum Number of Chimera Nodes for the Two-NAE3SAT Problem

Documentation for composites and samplers is here: dwave-system.

• Give this problem a try! Did you try and find it too hard, too easy, unclear? Please let us know -- we love your feedback.

Problem 10 is now posted too.

• 6 is the minimum number of nodes.

Here the code to prove it:

`from dwavebinarycsp import ConstraintSatisfactionProblem, SPIN, stitchfrom minorminer import find_embeddingdef nae3sat(a, b, c):    return not (a == b == c)csp = ConstraintSatisfactionProblem(SPIN)csp.add_constraint(nae3sat, ['a', 'b', 'c'])csp.add_constraint(nae3sat, ['c', 'd', 'e'])bqm = stitch(csp)chimera_cell = [(i, j + 4) for j in range(4) for i in range(4)]embeddings = [find_embedding(bqm.to_qubo()[0].keys(), chimera_cell) for i in range(10)]min_emb = min(embeddings, key=lambda x: len(sum(x.values(), [])))print(min_emb)print(len(sum(min_emb.values(), [])))`
• I have to agree with Jacob W, the minimum number of nodes is: 6

This is the output of the script:

Minimum embedding configuration: {'a': [3], 'b': [6], 'c': [4, 1], 'd': [7], 'e': [0]}
Minimum embedding length: 6
Verification of the found embedding
[-1, 1, 1, 1, -1] Occurrences: 3057 Energy: 0.0
[1, -1, 1, -1, 1] Occurrences: 1940 Energy: 0.0
[1, -1, -1, -1, 1] Occurrences: 2 Energy: 0.0
[-1, -1, 1, -1, -1] Occurrences: 1 Energy: 0.0
Bonus question: running in parallel
[-1, 1, 1, 1, -1] Occurrences: 2794 Energy: 0.0
[1, -1, 1, -1, 1] Occurrences: 2194 Energy: 0.0
[-1, 1, -1, 1, -1] Occurrences: 3 Energy: 0.0
[-1, 1, 1, -1, -1] Occurrences: 4 Energy: 0.0
[1, 1, -1, -1, 1] Occurrences: 1 Energy: 0.0
[-1, 1, 1, 1, -1] Occurrences: 2 Energy: 0.0
[-1, -1, 1, -1, -1] Occurrences: 1 Energy: 0.0
[-1, 1, -1, -1, 1] Occurrences: 1 Energy: 0.0
Adjacency: {'a': {'c', 'b', 'd'}, 'b': {'c', 'e', 'a'}, 'c': {'d', 'b', 'e', 'a'}, 'd': {'c', 'e', 'a'}, 'e': {'c', 'b', 'd'}}

The code is always on GitHub.

• Sorry, I was last. I also got six(6) as the answer.

I did try tiling across the entire Chimere structure, but the returned samples set comes with a single occurrence for each record, compared with single unit cell call. Can anyone comment on this?

BTW, awesome code by Jacob.

Below are the results and code. See you'll in Problem 10.

************ Methord 1 (Embedded in one unit cell) ***************
Neighbourhood check :
{'a': {'c', 'b', 'e'}, 'b': {'d', 'c', 'a'}, 'c': {'d', 'e', 'b', 'a'}, 'd': {'c', 'b', 'e'}, 'e': {'d', 'c', 'a'}}
BinaryQuadraticModel({'a': 0.0, 'b': 0.0, 'c': 0.0, 'd': 0.0, 'e': 0.0}, {('b', 'a'): 1.0, ('c', 'a'): 1.0, ('c', 'b'): 1.0, ('d', 'c'): 1.0, ('e', 'c'): 1.0, ('e', 'd'): 1.0}, 2.0, Vartype.SPIN)
[-1, 1, 1, -1, 1] Occurrences : 48 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 52 Energey : 0.0
************ Methord 2 (Tiled across a Chimera-structured sampler in multiple unit cell) ***************
Neighbourhood check :
{'a': {'c', 'b', 'e'}, 'b': {'d', 'c', 'a'}, 'c': {'d', 'e', 'b', 'a'}, 'd': {'c', 'b', 'e'}, 'e': {'d', 'c', 'a'}}
BinaryQuadraticModel({'a': 0.0, 'b': 0.0, 'c': 0.0, 'd': 0.0, 'e': 0.0}, {('b', 'a'): 1.0, ('c', 'a'): 1.0, ('c', 'b'): 1.0, ('d', 'c'): 1.0, ('e', 'c'): 1.0, ('e', 'd'): 1.0}, 2.0, Vartype.SPIN)
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0
[1, -1, 1, 1, -1] Occurrences : 1 Energey : 0.0
[-1, 1, 1, -1, 1] Occurrences : 1 Energey : 0.0...... and many more.............

https://github.com/yasasp/Dwave-Challenges/blob/master/dwc9.py

• Thank you for participating, and for the great answers. The answer is 6.