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.
D-Wave systems solve problems that can be mapped onto an Ising model or a quadratic unconstrained binary optimization (QUBO) problem.
is an objective function of \(N\) variables \(\vc s=[s_1,...,s_N]\) corresponding to physical Ising spins, where \(h_i\) are the biases and \(J_{i,j}\) the couplings between spins.
is an objective function of \(N\) binary variables represented as an upper-diagonal matrix \(Q\), where diagonal terms are the linear coefficients and the nonzero off-diagonal terms the quadratic coefficients.
The mapped problem must be formulated to be compatible with the constraints of the physical system and as robust as possible to analog control errors.
About this Document¶
This document provides guidance on the steps needed to solve a given problem (the problem instance) on the D-Wave system. It is structured, as shown in Table 3, to align with that workflow.
The steps in this workflow are designed to formalize the process of mapping problems onto the quantum processing unit (QPU) architecture and integrating solutions from the QPU into algorithms that solve given problems. It also provides references to technical documents, examples of prototype applications, and links to Ocean software tools.
Step in Workflow | Chapter | Software Tools | Examples | |
1 | Formulate the problem | Stating the Problem | State as a CSP or MAX-2-SAT (optimization); define an RBM (machine learning) | |
2 | Map to a supported formulation | Reformulating a Problem | Open-Source Software Tools | Reformulate an integer problem to use binary variables; convert a non-quadratic (high-order) polynomial to a QUBO |
3 | Decompose[1] and allocate to classical and quantum resources | Decomposing a Large Problem | Open-Source Software Tools | Use branch-and-bound methods to divide a large problem into smaller parts |
4 | Embed on QPU | Minor-Embedding a Problem | Open-Source Software Tools | Configure repeated elements and connect those with chained qubits |
5 | Configure the QPU | Sampling from the D-Wave QPU | Open-Source Software Tools | Use spin-reversal transforms to reduce errors; examine the annealing with reverse anneal |
[1] | For problems that require more qubits than available. |
A useful approach to this guide is to first scan through to see “the lay of the land.” New users may benefit from the introductory problems of the Background chapter, which walk through simple examples, before diving in to the more abstract descriptions of latter chapters. Otherwise, find the problem closest to your own field of work and follow that rather than peruse whole chapters.
Intended Audience¶
This document is for developers and researchers looking to deepen their understanding of solving problems on the D-Wave system.
It is assumed that new users have first read the Getting Started with the D-Wave System guide. Additionally, most new users are best served by first approaching quantum-computer programming through the demos and interactive examples in D-Wave’s Leap Quantum Application Environment and the documentation and examples the Ocean SDK provides.
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.
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}}\).
Abbreviations¶
Table 4 defines some of the abbreviations that are used throughout this document.
Abbreviation | Definition |
---|---|
BQP | Binary quadratic program |
CNF | Conjunctive normal form |
CSP | Constraint satisfaction problem |
DAC | Digital to analog converters |
EBM | Energy-based model |
ICE | Integrated control errors |
MIP | Mixed integer program |
MIS | Maximum independent set |
QA | Quantum annealing |
QMI | Quantum machine instruction |
QPU | Quantum processing unit |
QUBO | Quadratic unconstrained binary optimization |
SAPI | Solver Application Programming Interface (API) |
SAT | Satisfiability (problem) |
SSVM | Structured support vector machines |
SVM | Support vector machines |
VFYC | Virtual full-yield Chimera |
Key Terminology¶
It is assumed that new users have first read the Getting Started with the D-Wave System guide, which provides a full description of the following terminology that is used in this guide too. This section is meant as a reminder only.
Bias: the programmable quantity that controls the external magnetic field applied to a qubit. This field tilts the double-well potential, increasing the probability of the qubit ending up in the lower well.
Chimera: architecture of sets of connected unit cells, each with four horizontal qubits connected to four vertical qubits via couplers. Unit cells are tiled vertically and horizontally with adjacent qubits connected, creating a lattice of sparsely connected qubits. (The D-Wave 2000Q QPU supports a C16 Chimera graph: its 2048 qubits are logically mapped into a 16x16 matrix of unit cells of 8 qubits.) Figure 20 depicts the top leftmost 2x2 cells of a Chimera graph.
Coupler: can make two qubits tend to end up in the same state—both 0 or both 1—or it can make them tend to be in opposite states.
Ground state: lowest energy state during the anneal.
Hamiltonian (classical): a 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): a 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: The minimum distance between the ground state and the first excited state throughout any point in the anneal.
Minor embedding: the process of mapping logical qubits to physical qubits.
Objective function: a mathematical expression of the energy of a system as a function of binary variables representing the qubits.
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.
Qubits: quantum bits.