Getting incorrect results from QUBO - where is my error?

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?

0

Comments

4 comments
  • 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:

    2
    Comment actions Permalink
  • 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
  • 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
  • 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