Solving a large QUBO problem.
I am trying to solve a large QUBO problem. Can someone answer my questions:
1. What is the max variables I can use? Is it around 2000 (equivalent to the number of qubits)? In case I want to solve for more variables, what are some possible elegant solutions?
2. Are there any sparsity requirements on the binary interaction matrix J_{ij}? I can understand that the sparser the better, but are there any requirements/constraints based on the chimera graph architecture? I have very little knowledge of how the chimera graph structure relates to the type/complexity of QUBO problems that can be solved, so any resource on this will be great..
3. What are other alternate ways of inputting the weights ? I currently have the weights as numpy matrices... Is it imperative to convert into a dict? Or is there API *available* that can enable simply inputting the matrices circumventing the need to create a dict.
Any help will be greatly appreciated..
Comments
1.
The maximum number of variables you can use on the QPU corresponds to the number of active qubits on the QPU.
For more informationa about the number of qubits in the QPU please refer to this posting:
https://support.dwavesys.com/hc/en-us/articles/360009868993
(There is a note in 2. about the theoretical maximum number of fully connected qubits).
2.
To use all of the qubits on the QPU, your variables would have to be dependent according to the chimera graph structure:
https://docs.dwavesys.com/docs/latest/c_gs_4.html
Looking at the diagrams in the above link, you can see that not all qubits are coupled with one another.
In order to solve a more densely connected problem, you would have to minor-embed your problem onto the QPU.
This section of the documentation talks about minor-embedding:
https://docs.dwavesys.com/docs/latest/c_gs_7.html
This step can be done automatically with an EmbeddingComposite, which takes into account the shape of the QPU and attempts to map your problem onto it:
https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/composites.html#embeddingcomposite
The theoretical maximum number of fully connected qubits on the QPU is 65.
See the section called "Embedding Complete Graphs" on this page:
https://docs.dwavesys.com/docs/latest/handbook_embedding.html#embedding-complete-graphs
If you want to run more qubits than will fit on the QPU, you can try using a dwave-hybrid with a decomposer.
D-Wave Hybrid is very easy to install:
https://docs.ocean.dwavesys.com/projects/hybrid/en/latest/installation.html
Here is the reference documentation for using D-Wave Hybrid:
https://docs.ocean.dwavesys.com/projects/hybrid/en/latest/
Here is a reference to Decomposers:
https://docs.ocean.dwavesys.com/projects/hybrid/en/latest/reference/decomposers.html
Decomposers basically attempt to break the problem down systematically into pieces that can be run on the QPU.
You might even want to write your own decomposer that works well with your specific problem.
3.
The most straight forward way to input a numpy matrix to is to use the BinaryQuadraticModel (BQM) function from_numpy_vectors to create a BQM object and then use it as input to the sample function (instead of the sample_qubo function):
https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/generated/dimod.binary.BinaryQuadraticModel.from_numpy_vectors.html
Another good way to find information is by searching in the search box on the leap community page:
https://support.dwavesys.com/hc/en-us/community/topics
It does an extensive search of our resources, including community posts, documentation, and articles.
I hope this was all helpful.
Let us know if you have any further questions.
Hi Balaji,
Yesterday we launched Leap 2 and I am happy to tell you that it is now much easier to solve problems that are larger than a D-Wave 2000Q QPU. Please try using our new hybrid solver, which you will see on your Leap Dashboard as hybrid_v1. It accepts problems of up to 10,000 variables fully connected!
Submit the problem through Ocean as you would any other problem to the D-Wave system, but specify the new LeapHybridSampler in your Python program:
Take a look at our Knapsack example in Github, which is designed to demonstrate the usage of the hybrid solver.
Let us know how it goes,
Fiona
Please sign in to leave a comment.