Getting incorrect results from QUBO - where is my error?

Topias U

January 05, 2020 19:57

Hi,

I've been running this code:

mat = np.matrix([[-31,0,0,0,0],
[21,-29,0,0,0],
[18,18,-32,0,0],
[21,21,21,-29,0],
[18,18,21,18,-32]])

bqm = dimod.BinaryQuadraticModel.from_numpy_matrix(mat)

sampler = EmbeddingComposite(DWaveSampler()) #create a new sampler

response = sampler.sample(bqm, num_reads=10) #run our model with the sampler 10 times

And I get mostly as the result [1 0 1 1 1] with an energy of -7.

I think that even calculating by hand the correct solution should be [1 0 1 0 0] for an energy of -45.

([1 0 0 0 1] would be equally good)

What am I doing wrong?

Comments

4 comments

Alex K (Report)
January 07, 2020 23:44 (Edited January 07, 2020 23:45)
Hi Topias,

That's a good question! There are a couple of things that jump out. The first is the number of reads. Since the QPU is a probabilistic system it's better to do more reads. I would suggest starting at 1000.

The second thing is the chain strength. The default chain_strength is 1. Since your linear and quadratic terms have magnitudes between 18 and 32, you will get better results by matching the chain strength to that range.

Here's a comparison of your problem using a chain strength of 1 versus 20. For chain_strength=20 I omitted samples with small occurrences.
```
# Default chain strength
response = sampler.sample(bqm, chain_strength=1, num_reads=100)

print(response)
   0  1  2  3  4 energy num_oc. chain_.
0  1  1  1  0  1  -10.0      98     0.6
1  1  1  1  1  0   -1.0       2     0.6
['BINARY', 2 rows, 100 samples, 5 variables]
```
```
# Try chain_strength = 20
response = sampler.sample(bqm, chain_strength=20, num_reads=100)

print(response)
    0  1  2  3  4 energy num_oc. chain_.
0   1  0  1  0  0  -45.0      25     0.0
1   1  0  0  0  1  -45.0      13     0.0
2   0  1  0  0  1  -43.0      12     0.0
3   0  1  1  0  0  -43.0      21     0.0
4   0  0  0  1  1  -43.0      13     0.0
['BINARY', 13 rows, 100 samples, 5 variables]
```
One way to debug this issue is to look at the chain break occurrence (the last column in the printed response). If it is greater than 0 the chain strength needs to be larger.

I hope that helps! Here are a few resources that may be useful:
- These Usage Guidelines outline some general approaches for maximizing performance
- This Solving a Problem on the QPU guide describes a number of considerations and techniques that can improve results
- The problem embedding can impact results
2

Comment actions Permalink
Topias U (Report)
January 08, 2020 19:36

Thank you, Alex!

Perhaps the best forum answer I've gotten on any forum. :)

Didn't really understand the concept of the chains, but I get it now and probably get this to work correctly. Had the unfortunate good luck that my first QUBO attempts worked with the default chain strength, so I kinda skipped over it.

Br,

Topias

0

Comment actions Permalink
Alex K (Report)
January 08, 2020 20:39

Chains are tricky, especially when it comes to understanding how their configuration and the chain strength can impact results :) I'm glad that helped!

1

Comment actions Permalink
Richard W (Report)
January 11, 2020 18:05

Thanks this answer was super helpful. I was finding my problem worked for a smaller version and stopped working as I increased the size of the problem, increasing the chain_strength to match the magnitude of the different between terms immediately improved the result accuracy :).

1

Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post