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

Fiona H

March 09, 2019 15:47

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.

Comments

8 comments

Jacob W (Report)

March 10, 2019 01:39 (Edited March 10, 2019 01:58)

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}%")

Calogero Z (Report)
March 11, 2019 06:25

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
Fiona H (Report)
March 11, 2019 16:13

Apologies for the broken link. I've restored the image.

0

Comment actions Permalink
Yasas P (Report)
March 14, 2019 14:10

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
Calogero Z (Report)
March 17, 2019 09:47

My answer is that the number of Ground States is 10

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
Fiona H (Report)
March 17, 2019 18:15 (Edited March 18, 2019 15:53)

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
Fiona H (Report)
March 22, 2019 20:58 (Edited March 22, 2019 20:58)

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
Calogero Z (Report)
March 23, 2019 08:30

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