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 the D-Wave System 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. 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 6, 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 the D-Wave System 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, new users are advised to read the Getting Started with the D-Wave System guide. Explanations of terminology in this section is meant as a reminder.
Bias: Programmable value that controls the likelihood a qubit ends the anneal in the +1 or -1 state.
Chimera: D-Wave QPUs are lattices of interconnected qubits. While some qubits connect to others via couplers, the QPU is not fully connected. Instead, qubits interconnect in a particular topology, one known as Chimera on D-Wave 2000Q systems, and another known as Pegasus on Advantage systems.
Coupling: Programmable value that controls the likelihood that two qubits end up in the same state—both -1 or both 1—or opposite states.
Ground state: Lowest energy state during the anneal.
Hamiltonian (classical): Mathematical description of some physical system in terms of its energies. Input any particular state of the system, and the Hamiltonian returns the energy for that state.
Hamiltonian (quantum): Function that maps certain states, called eigenstates, to energies. Only when the system is in an eigenstate of the Hamiltonian is its energy well defined and called the eigenenergy. When the system is in any other state, its energy is uncertain. The collection of eigenstates with defined eigenenergies make up the eigenspectrum.
Minimum gap: Minimum difference between the ground state and the first excited state throughout any point in the anneal.
Minor embedding: Process of mapping variables to physical qubits.
Objective function: Mathematical expression of the energy of a system as a function of binary variables representing the qubits.
Pegasus: D-Wave QPUs are lattices of interconnected qubits. While some qubits connect to others via couplers, the QPU is not fully connected. Instead, qubits interconnect in a particular topology, one known as Chimera on D-Wave 2000Q systems, and another known as Pegasus on Advantage systems.
Quantum annealing: Harnesses the natural evolution of quantum states: you initialize the system in a delocalized state, gradually turn on the description of the problem you wish to solve, and quantum physics allows the system to follow these changes. The configuration at the end corresponds to the answer you are trying to find.
QPU: quantum processing unit.
Qubits: quantum bits.