Solutions differ between neal and QPU
Hi,
I'm still rather new to QC. I have found a way to implement an optimization problem (basically a matrix multiplication) into the QUBO formulation. The solution I want to obtain is a string of binary numbers in the (0,1) representation that are later interpreted as N integers. It follows the treatment described in [O'Malley and Vesselinov]. The QPU is a chimera graph (16x16x4).
If I run the optimization with neal, I always find the exact solution to Ax=y. However, if I use the QPU, it never finds the minimum even if I execute up to 10,000 cycles. By comparing the energy found by the QPU to the exact solution, they are numerically close but not the same, and bit-wise the two solutions do not really match. Interestingly, if I force the QPU to start from the state found by neal, and run a reverse annealing, the system remains in the same minimum.
I'm not sure what is causing this issue. I wonder if more experienced users can point me to similar examples where this behaviour was observed before, or can give me any useful suggestion to track down the origin of the problem.
Best,
Riccardo
Comments
There are a number of reasons the QPU might have a hard time finding the ground/lowest energy state.
Often this happens when there are energy states clustered together, rather than being spread out evenly, especially when there are multiple energy states close to the ground state.
The best solution for this is to carefully design the input problem to avoid multiple states close to ground.
Another potential area where errors might arise is with the chains that are created when embedding the problem.
The process of mapping the logical qubits of the problem to the physical qubits of the chip is called "minor-embedding".
Here is a link to the documentation on the Chimera graph structure of the QPU:
https://docs.dwavesys.com/docs/latest/c_gs_4.html
Here is a link to documentation on minor-embedding to better understand the actual form it takes:
https://docs.dwavesys.com/docs/latest/c_gs_7.html
Chains of uneven length can "freeze out" (i.e. decide on their value) at different times during the anneal cycle, long chains freezing out earlier than shorter chains.
Here is a link to some documentation that talks about chains and how they interact with the anneal schedule (At the end of "Anneal Offsets"):
https://docs.dwavesys.com/docs/latest/c_qpu_annealing.html?highlight=anneal%20offsets#anneal-offsets
Having a densely connected input graph (i.e. a complete QUBO matrix) will increase the length of the chains.
Creating a BinaryQuadraticModel from a QUBO matrix in the form of numpy vectors can help to mitigate some of this issue, as 0 biases will be excluded from the input and the embedding can be treated as a more sparsely populated graph.
Here is a link to the documentation for dimod.BinaryQuadraticModel.from_numpy_vectors:
https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/generated/dimod.binary.BinaryQuadraticModel.from_numpy_vectors.html
Inputting every 0 bias that is in the matrix into a dictionary will cause a very densely connected input graph.
The results you are seeing make sense, as reverse annealing will not cause the energy level to go up, but rather look for more optimal answers (which it will not find in this case).
This being a physical machine, problem formulation plays a very big role, and can make the difference between being able to find the problem easily or not.
The neal solver will also try to find the lowest energy state, but as problems become more complex, it will take longer and longer.
Another popular method to finding the ground state is to start by using the QPU and then use classical computing to search the nearby area around the solution returned.
Here is a link to the Github code associated with this method:
https://github.com/dwavesystems/dwave-hybrid/blob/master/examples/tabu-postprocessing.py
This code uses another library called dwave-hybrid, which allows processes to be stringed together and results to be fed along the chain and even back into a loop.
I hope this was helpful.
Hi,
thanks for the reply, I'm sorry it took such a long time for me to process this information. I moved from the dictionary-based to the numpy-array-based approach as you suggested. You can find below an example of the coefficients matrix, I'm not sure if this looks to you like a dense matrix. Also, I create chains using minorminer.find_embedding() and solve the problem using the FixedEmbeddingComposite solver. The best embedding I find has a maximum chain length of 7. Again, I'm not completely sure if this counts as a long chain, or can still be considered short. The minimum is never exactly found by the QPU (it works instead if I use neal, as reported before), not even if I run the optimization 5000 times. I also tried a custom annealing schedule (holding the annealing for 100 us), but I haven't seen any improvement wrt the default one of 20 us. I'm kind of running out of ideas, mostly because I'm having a hard time to grasp what the origin of the problem actually is.
Best,
Riccardo
[[ -704. 128. 64. 32. 384. 192. 96. 48. 128. 64. 32. 16. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. -384. 32. 16. 192. 96. 48. 24. 64. 32. 16. 8. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. -200. 8. 96. 48. 24. 12. 32. 16. 8. 4. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. -102. 48. 24. 12. 6. 16. 8. 4. 2. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. -1888. 384. 192. 96. 640. 320. 160. 80. 128. 64. 32. 16. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. -1040. 96. 48. 320. 160. 80. 40. 64. 32. 16. 8. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. -544. 24. 160. 80. 40. 20. 32. 16. 8. 4. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. -278. 80. 40. 20. 10. 16. 8. 4. 2. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 0. -2928. 704. 352. 176. 768. 384. 192. 96. 128. 64. 32. 16.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. -1640. 176. 88. 384. 192. 96. 48. 64. 32. 16. 8.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -864. 44. 192. 96. 48. 24. 32. 16. 8. 4.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -443. 96. 48. 24. 12. 16. 8. 4. 2.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -1808. 704. 352. 176. 640. 320. 160. 80.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -1080. 176. 88. 320. 160. 80. 40.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -584. 44. 160. 80. 40. 20.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -303. 80. 40. 20. 10.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -528. 320. 160. 80.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -344. 80. 40.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -192. 20.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -101.]]
The crux of the issue is most likely that the energy states are bunched close together, and possibly also close to the ground state, rather than being evenly spaced out.
This is a difficult problem to address, as it often has to do with problem formulation itself.
A chain length of 7 is starting to get long, but in some cases is quite reasonable.
Another thing about chains is their length relative to one another.
Longer chains tend to freeze out on a value earlier in the anneal schedule.
For that reason, creating an anneal schedule that shifts the anneal time of specific chains to a time later in the schedule can help to change the dynamics of the energy landscape.
To fine-tune the anneal schedule, the individual qubits need to be assigned schedules, which can be made possible by using the embedding to determine which chains are longer and which qubits belong in each chain.
Here are a couple of community posts that relate to adjusting the anneal schedule:
https://support.dwavesys.com/hc/en-us/community/posts/360016680754
https://support.dwavesys.com/hc/en-us/community/posts/360014009713
I hope this was helpful.
Please let us know if you have any more questions, and let us know if this information was useful.
Please sign in to leave a comment.