Introduction¶
Quantum computing has the potential to help solve some of the most complex technical, scientific, national defense, and commercial problems that organizations face. For quantum computing, as for classical, the first step in solving a problem is to express it in a mathematical formulation compatible with the underlying physical hardware.
As explained in the Getting Started with D-Wave Solvers guide, to solve a problem on D-Wave solvers you formulate the problem as an objective function, usually in Ising or quadratic unconstrained binary optimization (QUBO) format if you are submitting to a quantum sampler (Leap’s quantum-classical hybrid solvers accept additional quantum models). Low energy states of the objective function represent good solutions to the problem. For QPU solvers, you map the objective to the QPU topology (minor-embedding): linear coefficients to qubit biases and quadratic coefficients to coupler strengths. The solver seeks the minimum of the resulting energy landscape—QPU solvers do so with quantum annealing—and that corresponds to the solution of your problem.
For example, if your problem was to optimize router placement in a communications network, you might begin by stating the problem as a vertex cover; that is; you state the problem of where best to place the routers, mathematically, as the graph problem of finding a set of vertices, which represents routers, that includes at least one endpoint of the graph’s every edge, with edges representing optical fibers. To solve it, you might reformulate the vertex cover as a QUBO and submit that to a solver.
The vertex cover example in the Ocean documentation does this for an illustrative five-node problem, with Ocean tools returning a solution to an internally formulated objective function:
>>> from dimod.reference.samplers import ExactSolver
>>> import networkx as nx
>>> import dwave_networkx as dnx
...
>>> # Create a star graph where node 0 is hub to four other nodes
>>> s5 = nx.star_graph(4)
>>> # Select an Ocean test sampler
>>> sampler = ExactSolver()
>>> print(dnx.min_vertex_cover(s5, sampler))
[0]
For this five-node network, placing a router at node 0 enables communication with all the network’s nodes.
Most real-world problems are not so easily solved. Formulating the problem can be challenging[1] and finding good solutions to the formulated problem might also require work to correctly configure the solver.
[1] | See [Jor2011] for example. |
About this Document¶
This document is a reference guide to the steps needed to solve problems on D-Wave solvers, in general, and directly on D-Wave’s quantum computers, in particular. It is structured, as shown in Table 4, to align with the problem-solving workflow. Quantum-classical hybrid solvers, such as those hosted in Leap or provided by Ocean’s dwave-hybrid Python development framework, handle some of the steps you need for direct use of quantum computers, but still require an appropriately formulated problem.
Step in Workflow | Chapter | Examples | |
---|---|---|---|
1 | Formulate the problem | Stating the Problem | A CSP or vertex cover. |
2 | Map to a supported format | Reformulating a Problem | A binary quadratic model, a QUBO, or a discrete quadratic model. |
For Hybrid Solvers: | |||
3 | Configure the hybrid solver | Using Hybrid Solvers | Set a long enough time_limit to reach the needed quality of solutions. |
For QPU Solvers: | |||
3 | Decompose and allocate | QPU Solvers: Decomposing Large Problems | Divide a large problem into smaller parts allocated to classical and quantum resources. |
4 | Embed on QPU | QPU Solvers: Minor-Embedding | Embed a sequence of similar problems in a reusable clique embedding with
a DWaveCliqueSampler solver. |
5 | Configure the QPU | QPU Solvers: Configuration | Set anneal_offsets for precision controlling of the anneal. |
The steps in this workflow are designed to formalize the process of effectively formulating problems for D-Wave solvers, especially the quantum processing unit (QPU). It also provides code examples, references to technical or academic documents, and links to examples of prototype applications.
Intended Audience¶
This document is for developers and researchers looking to deepen their understanding of solving problems on D-Wave solvers, especially directly on D-Wave quantum computers, which requires more knowledge than hybrid solvers.
The problems solved on quantum computers are often highly complex and some problems may belong to research fields that require specific domain knowledge. Although a full understanding of the formulations presented in this guide can require a strong backgrounding in combinatorial methods, logic, and so on, you may be able to solve a given problem with just one or two relevant techniques. Additionally, Ocean software provides open-source tools that take care of the underlying algorithms.
It is assumed that new users have first read the Getting Started with D-Wave Solvers guide.
Notation¶
Unless specified otherwise:
- Vectors are indicated in lowercase bold font; e.g. \(\vc{s}=[s_1, \cdots, s_n]\).
- Matrices are indicated in uppercase bold font; e.g., \(\vc{Q}\).
- Euclidean inner product of vectors is indicated with angular brackets; e.g., for \(\vc{a}\) and \(\vc{b}\), it is \(\ip{\vc{a}}{\vc{b}}\).
Key Terminology¶
For basic explanations of quantum computing, read the Getting Started with D-Wave Solvers guide. Ocean documentation provides a glossary.