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

• 

  Fiona H  (Report)

  March 22, 2019 20:26 (Edited March 22, 2019 20:39)

  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
• 

  Jacob W  (Report)

  March 22, 2019 21:41

  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
• 

  Calogero Z  (Report)

  March 24, 2019 10:34

  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
• 

  Yasas P  (Report)

  March 27, 2019 04:22

  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
• 

  Fiona H  (Report)

  March 29, 2019 23:08

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

  0

  Comment actions Permalink

Please sign in to leave a comment.