Problem 8: Find Ground States for an Ising Model of Two CSPs

 

As mentioned in the previous problem, CSPs such as scheduling can be hard problems. See this technique used on a scheduling problem at Constrained Scheduling.

Here is the documentation for dwavebinarycsp.

0

Comments

8 comments
  • Answer: 18

    The Hamiltonian for this problem consists of two parts. Each part is NAE3SAT(problem 7). Ground states must satisfy both constraints at the same time(min(Ha + Hb) = min(Ha) + min(Hb)). The first constraint gives 6 ground states for a, b, c spins. After that, we have c spin that has been fixed, so the second condition gives 3 ground states(e.g. if c is equal to 1, then ground states are [1, 1, -1], [1, -1, 1], [1, -1, -1] for c, d, e spins respectively). Using simple combinatorics, we get 6*3=18 ground states.

    Here is the code:

    from dimod import BinaryQuadraticModel, SPIN
    from neal import SimulatedAnnealingSampler

    bqm = BinaryQuadraticModel(
    linear={}, offset=0, vartype=SPIN,
    quadratic={
    ('a', 'b'): 1, ('a', 'c'): 1, ('b', 'c'): 1,
    ('c', 'd'): 1, ('c', 'e'): 1, ('d', 'e'): 1
    }
    )

    shots = 1000
    sampler = SimulatedAnnealingSampler()
    response = sampler.sample(bqm, num_reads=shots)

    results = {}
    for datum in response.data(['sample', 'energy', 'num_occurrences']):
    key = hash(frozenset(datum.sample.items()))
    if key in results:
    results[key] = {
    'sample': datum.sample, 'energy': datum.energy,
    'probability': results[key]['probability'] + datum.num_occurrences/shots*100
    }
    else:
    results[key] = {
    'sample': datum.sample, 'energy': datum.energy,
    'probability': datum.num_occurrences/shots*100
    }

    for key in results:
    print(f"{results[key]['sample']}, energy: {results[key]['energy']}, "
    f"probability: {results[key]['probability']:.2f}%")

     

    1
    Comment actions Permalink
  • Fiona, there is a broken image in your post, that I'm not able to see :(

    Can you please fix it?

    Thank you very much!

    Cal

    0
    Comment actions Permalink
  • Apologies for the broken link. I've restored the image.

    0
    Comment actions Permalink
  • The answer is 18 ground states. This was obtained from the classical solver. When submitted to the QPU, all the ground states were not returned and also the number of occurrences is irregular for the ground states.

    Below are the code and the result screen.

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

    ************ Methord 1 (Classical Solver) ***************
    [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
    [-1, -1, -1, 1, -1] Occurrences : 1 Energey : 4.0
    [1, 1, 1, -1, 1] Occurrences : 1 Energey : 4.0
    [-1, -1, 1, 1, 1] Occurrences : 1 Energey : 4.0
    [1, -1, 1, 1, 1] Occurrences : 1 Energey : 4.0
    [-1, -1, -1, -1, 1] Occurrences : 1 Energey : 4.0
    [-1, 1, 1, 1, 1] Occurrences : 1 Energey : 4.0
    [-1, -1, -1, 1, 1] Occurrences : 1 Energey : 4.0
    [1, 1, 1, 1, -1] Occurrences : 1 Energey : 4.0
    [1, 1, 1, -1, -1] Occurrences : 1 Energey : 4.0
    [-1, 1, -1, -1, -1] Occurrences : 1 Energey : 4.0
    [1, 1, -1, -1, -1] Occurrences : 1 Energey : 4.0
    [1, -1, -1, -1, -1] Occurrences : 1 Energey : 4.0
    [1, 1, 1, 1, 1] Occurrences : 1 Energey : 8.0
    [-1, -1, -1, -1, -1] Occurrences : 1 Energey : 8.0
    ************ Methord 2 (QPU) ***************
    [1, -1, 1, -1, 1] Occurrences : 2947 Energey : 0.0
    [-1, 1, 1, 1, -1] Occurrences : 2043 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
    linear parameters : {'a': 0.0, 'b': 0.0, 'c': 0.0, 'd': 0.0, 'e': 0.0}
    quadratic parameters : {('b', 'a'): 1.0, ('c', 'a'): 1.0, ('c', 'b'): 1.0, ('d', 'c'): 1.0, ('e', 'c'): 1.0, ('e', 'd'): 1.0}
    offset parameter : 2.0
    ************ Methord 3 (QPU) ***************
    [-1, 1, 1, 1, -1] Occurrences : 2401 Energey : 0.0
    [1, -1, 1, -1, 1] Occurrences : 2588 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 : 2 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 : 2 Energey : 0.0
    [-1, 1, 1, 1, -1] Occurrences : 1 Energey : 0.0

    1
    Comment actions Permalink
  • My answer is that the number of Ground States is 10

    Here is the code on github:

    https://github.com/CalogeroZarbo/quantum_training/blob/master/dwave_problem8.py


    This is the configuration of the BQM that reflect the picture:

    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)


    This is the output of the possible ground states found in 5000 shots:

    [1, -1, 1, 1, -1] Occurrences: 2255 Energy: 0.0
    [-1, 1, 1, -1, 1] Occurrences: 2730 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: 2 Energy: 0.0
    [1, 1, -1, 1, 1] Occurrences: 3 Energy: 0.0
    [-1, -1, 1, -1, -1] Occurrences: 2 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: 2 Energy: 0.0

    1
    Comment actions Permalink
  • Thanks to those who submitted answers to Problem 8! The answer we're looking for is 18 ground states. Correct answers from Jacob and Yasas.  Problem 9 is now up.

    0
    Comment actions Permalink
  • Calogero, your answer is also good! 

    Sorry for the delay in posting it (any post that contains a link needs to be approved before it appears here, so it didn't show up until after I posted the answer even though you submitted it before).  

    0
    Comment actions Permalink
  • Thank you Fiona!

    Actually I understood my bad was to forget about the stochastic nature of the QPU, that of course doesn't show up all the possibilities, but only the most probable. However it was a good lesson for me, and this is the most important thing.

    Thank you also for caring about the coding challenge, it is slowly putting me in the right mindset to build application on top of a Quantum Computer :)

    1
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post