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

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

1

Comments

5 comments
  • 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.

    0
    Comment actions Permalink
  • 6 is the minimum number of nodes.

     

    Here the code to prove it:

    from dwavebinarycsp import ConstraintSatisfactionProblem, SPIN, stitch
    from minorminer import find_embedding

    def 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(), [])))
    1
    Comment actions Permalink
  • 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.

    1
    Comment actions Permalink
  • 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

     

    1
    Comment actions Permalink
  • Thank you for participating, and for the great answers. The answer is 6. 

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post