Using Hybrid and Classical Solvers#
D-Wave’s quantum-classical hybrid solvers are designed to simplify the incorporation of quantum computing into problem-solving applications and Ocean software’s classical solvers often require fewer or simpler steps to use than directly using quantum computers. Both make good starting points in developing your application code, and this section provides some usage guidance.
Classical solvers are useful for testing code during development but might not be sufficiently performant on the hard problems of a production application. At that point in your code development you might incorporate either a QPU solver or a hybrid solver.
D-Wave offers two complementary approaches to quantum-classical hybrid computing, Leap’s Hybrid Solvers and the dwave-hybrid Hybrid Framework.
Classical solvers may be determinstic or heuristic. Typically such solvers are unstructured, meaning you do not have to map the connectivity of your problem’s variables to a working graph of the solver (as you would minor-embed problems for a quantum computer). Ocean software provides a variety of classical solvers that run locally on your CPU. Some are designed to help with code development and debugging by deterministically solving small problems, others can performantly provide good solutions to a wide range of problems.
Reformulation#
Some of the guidance detailed in the General Guidance on Reformulating section applies to all solvers, especially those that accept binary quadratic models. Although, for example, limitations on problem size are vastly expanded compared to QPU solvers, formulations that proliferate ancillary variables might still perform less well than alternative formulations.
Leap’s Hybrid Solvers#
D-Wave’s Leap quantum cloud service provides cloud-based hybrid solvers you can submit arbitrary quadratic and nonlinear models to. These solvers, which implement state-of-the-art classical algorithms together with intelligent allocation of the quantum processing unit (QPU) to parts of the problem where it benefits most, are designed to accommodate even very large problems. Leap’s hybrid solvers enable you to benefit from D-Wave’s deep investment in researching, developing, optimizing, and maintaining hybrid algorithms.
The Using Leap’s Hybrid Solvers page provides basic information on these solvers and pointers to relevant documentation on properties, parameters, timing, etc.
The following guidance applies to Leap’s hybrid solvers.
Large-Problem Construction#
For large problems, attention should be given to the total number of symbols for nonlinear models and biases for quadratic models. Generating models with huge numbers of symbols or biases may exhaust resources such as memory on your local machine and uploads to Leap may tax your connection’s bandwidth.
To enable best performance of your local machine and application, consider such points as the following:
Before constructing extremely large problems, verify that your local machine has sufficient resources (such as memory) to support possibly millions of biases.
Problems can be formulated with more performant software structures such as BQMs or models built from NumPy arrays rather than Python lists.
See dimod for examples.
Uploading huge problems to Leap can take time and may require significant bandwidth from your Internet link. Consider using compression where supported by your selected hybrid solver.
Run Times#
Hybrid solvers enable you to configure the time the solver runs your problem.
For many heuristic solvers, solution quality as a function of runtime is highly dependent on the problem being solved. Consequently, hybrid solvers can set a default runtime that is either short and insufficient for many problems or long and expensive for many problems. Leap’s hybrid solvers set as the default runtime a minimum time based on the number of problem variables (and possibly additional measures of the problem’s complexity, such as connectivity).
Running a hybrid solver with the default time_limit parameter does not guarantee a good solution.
Depending on the size and complexity of your problem, there are a number of strategies you can use for setting appropriate runtimes.
Use the default, see if the returned solutions are good enough for your needs. If not, keep doubling the runtime until good solutions are produced or solutions remain unchanged.
Set a runtime based on experiments with similar problems.
Set a runtime based on considerations of the context in which your application runs: cost, available time for processing, solution quality required, etc.
Further Information#
dwave-hybrid Hybrid Framework#
Ocean software’s dwave-hybrid provides you with a Python framework for building a variety of flexible hybrid workflows. These use quantum and classical resources together to find good solutions to your problem. For example, a hybrid workflow might use classical resources to find a problem’s hard core and send that to the QPU, or break a large problem into smaller pieces that can be solved on a QPU and then recombined.
The dwave-hybrid framework enables rapid development of experimental prototypes, which provide insight into expected performance of the productized versions. It provides reference samplers and workflows you can quickly plug into your application code. You can easily experiment with customizing workflows that best solve your problem. You can also develop your own hybrid components to optimize performance.
The dwave-hybrid framework and its reference solvers enable a higher degree of user control than Leap’s hybrid solvers. Whether you are developing your own hybrid workflows or tuning the performance of provided dwave-hybrid solvers, your solutions may benefit from applying some of the guidance of the QPU Solvers: Decomposing Large Problems, QPU Solvers: Minor-Embedding, and QPU Solvers: Configuration chapters.
Further Information#
For documentation, see the dwave-hybrid documentation.
The Hybrid Computing Jupyter Notebooks explain and demonstrate how to develop and use the dwave-hybrid hybrid solvers and development framework.
Deterministic Classical Solvers#
During code development and debugging, it can be helpful to have the capability to exactly solve small test problems, to ensure the best solution is in fact the global optimum and display the energy gaps between states.
Solvers such as dimod‘s
ExactSolver
and
ExactPolySolver
brute-force solve problems,
making them slow on any but small problems. For testing, however, they can be
invaluable.
Example#
This example calculates the energies of the ground and excited states of a small (three variables) binary quadratic model representing a Boolean AND gate.
>>> import dimod
>>> bqm = dimod.generators.and_gate("x1", "x2", "z")
>>> len(bqm.variables)
3
>>> print(dimod.ExactSolver().sample(bqm))
x1 x2 z energy num_oc.
0 0 0 0 0.0 1
1 1 0 0 0.0 1
3 0 1 0 0.0 1
5 1 1 1 0.0 1
2 1 1 0 1.0 1
4 0 1 1 1.0 1
6 1 0 1 1.0 1
7 0 0 1 3.0 1
['BINARY', 8 rows, 8 samples, 3 variables]
Heuristic Classical Solvers#
While solutions produced by deterministic solvers are guaranteed to include the problem’s ground states (globally optimal solution), such solvers are limited to small-sized problems. Classical heuristic solvers can solvers much larger problems and can often do so performantly.
Ocean software provides heuristic classical solvers that implement various algorithms, such as simulated annealing (dwave-neal), tabu search (dwave-tabu), and steepest descent (dwave-greedy).
Examples#
This example finds a maximum independent set on a 77-node graph with two different hueristic classical samplers and validates the best solution found by comparison.
>>> import networkx as nx
>>> import dimod
>>> from neal import SimulatedAnnealingSampler
>>> from tabu import TabuSampler
...
>>> G = nx.generators.les_miserables_graph()
>>> bqm = dimod.generators.maximum_independent_set(G.edges, G.nodes)
>>> len(bqm)
77
>>> sampleset_sa = SimulatedAnnealingSampler().sample(bqm, num_reads=10)
>>> sampleset_tabu = TabuSampler().sample(bqm, num_reads=100)
>>> sum(sampleset_sa.first.sample.values())
35
>>> sum(sampleset_tabu.first.sample.values())
35
>>> [key for key, val in sampleset_sa.first.sample.items() if val][0:5]
['Anzelma', 'BaronessT', 'Boulatruelle', 'Brujon', 'Champtercier']
Further Information#
[Koh2022] shows how quantum annealing provides an exponential improvement over simulated annealing for an optimization problem with a one-dimensional continuous degree of freedom.