# 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.

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, SPINfrom neal import SimulatedAnnealingSamplerbqm = 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 = 1000sampler = 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}%")`

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

Thank you very much!

Cal

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

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

************ 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

• 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

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