1
$\begingroup$

I implemented a solver for the Job Shop Problem, based on quantum annealing, on a D-Wave machine.

I have a problem, that even though minimal energy solutions exist, they are only chosen once. I set the nbr of reads to 1000, but the responses still look like this: 

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ... 41 energy num_oc. ...
0    1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0 ...  1 -144.0       1 ...
1    0  1  0  0  0  0  0  0  0  0  0  0  0  0  1  0 ...  1 -136.0       1 ...
2    1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0 ...  1 -134.0       1 ...
15   1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0 ...  0 -133.0       1 ...
16   1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...  0 -133.0       1 ...
138  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0 ...  0 -131.0       1 ...
3    1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0 ...  1 -129.0       1 ...
4    0  1  0  0  0  0  0  0  0  0  0  1  0  0  0  0 ...  0 -127.0       1 ...

Should't the lowest energy solution, get picked more than once, just by chance?

On multiple runs, I now always get a different, kind of random result it seems.

I tried playing around with the chain strength, up to a point where no chains are breaking anymore, so I think it should be at a good spot right now.

Do you have any idea, what the issue might be?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There is no guarantee the lowest energy solution get picked more often, or even get picked once.

Many parameters may be tweaked in order to improve your results. I am not sure if you are running time parameters by default but you may tweak more the times (like longer annealing time...).

Secondly, it may be the case that this problem corresponds to a hard one for the annealer (requires too many qubits when embedding your problem, or/and that this problem has a minimal spectral gap very small where it is more for quantum annealing...). Maybe what you could do is try fixing a few variables from the exact solution, and see if you still miss too often the exact solution. You may also have mistakes when setting your problem as a QUBO, which I would recommend debugging it well in order to be sure.

Finally, you may try a good classical heuristic for this problem and check you find a good solution, and see if the annealer improves against it.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi cnada, thanks for your help :) I increased the annealing_time, but got the same results. The QUBO is only 42 x 42, so should easily fit on DW_2000Q_5. Could you elaborate what you mean with " fixing a few variables from the exact solution, and see if you still miss too often the exact solution" please? I don't quite understand. $\endgroup$
    – Robinbux
    Commented Mar 9, 2020 at 11:59
  • $\begingroup$ @Robinbux Basically, you can create a new QUBO by fixing a few variables being equal to the values of the solution. Like say you fix variable $x_2=1, x_3 = 0, x_4 = 1$ as the solution of the problem have these values, get a new QUBO that does not account $x_2,x_3,x_4$ as variables and solve it with the annealer. The solution returned should hopefully match the seeked solution without $x_2,x_3, x_4$. Choosing variables to be fixed is up to you, but this can be a way of debugging. $\endgroup$
    – cnada
    Commented Mar 9, 2020 at 12:06
  • $\begingroup$ But my QUBO represents my energy, rather than the solution right? I have my qubo matrix, telling me the "punishment" of picking x3, if x1 is picked for example, and out of this QUBO the qubits should collaps into the lowest engery state, out of my understanding. How could I revert this process, by manually picking the right solution? If I chose like you said $x_0 = 0, x_1 = 1, x_2 = 0 ...$ I would still need to get my 42x42 matrix out of this, right? $\endgroup$
    – Robinbux
    Commented Mar 9, 2020 at 13:21
  • $\begingroup$ @Robinbux Yes it does but it is just that you may have too many variables for the annealer, or that is a hard instance for it. So my advice would be to do a bit of preprocessing like setting a few variables to go from 42*42 qubo to a bit less like 25*25 qubo or less and see if it is able to find the other variables values that would be the rest of the solution. This is done heuristically when you divide a problem into subproblems or sometimes when we know that a variable takes often the same value, we fix it in the qubo formulation to remove it from the set of variables we optimize on. $\endgroup$
    – cnada
    Commented Mar 9, 2020 at 16:41
  • $\begingroup$ I was trying again with a very small example, as you suggested, and discovered that the exact same results are simply not added together for some reason $\endgroup$
    – Robinbux
    Commented Mar 10, 2020 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.