Solving Problems with D-Wave Solvers

The previous chapter explained how the D-Wave QPU uses quantum annealing to find the minimum of an energy landscape defined by the biases and couplings applied to its qubits in the form of a problem Hamiltonian. To solve a problem on the system, you formulate this problem Hamiltonian such that when the system finds its minimum, it is finding solutions to your problem.

This section provides a conceptual framework for formulating problems for D-Wave solvers; the key concepts are objective functions, Ising model, quadratic unconstrained binary optimization problems (QUBOs), graphs, and minor embedding.

Objective Functions

To express a problem for a D-Wave solver in a form that enables solution by minimization, you need an objective function, a mathematical expression of the energy of a system. When the solver is a QPU, the energy is a function of binary variables representing its qubits; for quantum-classical hybrid solvers, the energy might be a more abstract function.

Energy of objective function.

Fig. 9 Energy of the objective function.

For most problems, the lower the energy of the objective function, the better the solution. Sometimes any low-energy state is an acceptable solution to the original problem; for other problems, only optimal solutions are acceptable. The best solutions typically correspond to the global minimum energy in the solution space; see Figure 9.

As an illustrative example, consider the equation \(x+1=2\). To solve it by minimization, you can formulate the objective function \(\min_x[2-(x+1)]^2\) by taking the square of the subtraction of one side from another. Minimization seeks the shortest distance between the sides, which occurs at equality (with the square eliminating negative distance).

For the QPU, two formulations for objective functions are the Ising Model and QUBO. Both these formulations are binary quadratic[1] models (BQM) and conversion between them is trivial[2].

[1]

Quadratic functions have one or two variables per term. A simple example of a quadratic function is,

\[D = Ax + By + Cxy\]

where \(A\), \(B\), and \(C\) are constants. Single variable terms—\(Ax\) and \(By\) here—are linear with the constant biasing the term’s variable. Two-variable terms—\(Cxy\) here—are quadratic with a relationship between the variables.

[2]Chapter Appendix: Next Learning Steps provides information on the differences and conversion between the two formulations.

Ising Model

The Ising model is traditionally used in statistical mechanics. Variables are “spin up” (\(\uparrow\)) and “spin down” (\(\downarrow\)), states that correspond to \(+1\) and \(-1\) values. Relationships between the spins, represented by couplings, are correlations or anti-correlations. The objective function expressed as an Ising model is as follows:

\[\text{E}_{ising}(\vc s) = \sum_{i=1}^N h_i s_i + \sum_{i=1}^N \sum_{j=i+1}^N J_{i,j} s_i s_j\]

where the linear coefficients corresponding to qubit biases are \(h_i\), and the quadratic coefficients corresponding to coupling strengths are \(J_{i,j}\).

QUBO

QUBO problems are traditionally used in computer science, with variables taking values 1 (TRUE) and 0 (FALSE).

A QUBO problem is defined using an upper-diagonal matrix \(Q\), which is an \(N\) x \(N\) upper-triangular matrix of real weights, and \(x\), a vector of binary variables, as minimizing the function

\[f(x) = \sum_{i} {Q_{i,i}}{x_i} + \sum_{i<j} {Q_{i,j}}{x_i}{x_j}\]

where the diagonal terms \(Q_{i,i}\) are the linear coefficients and the nonzero off-diagonal terms \(Q_{i,j}\) are the quadratic coefficients.

This can be expressed more concisely as

\[\min_{{x} \in {\{0,1\}^n}} {x}^{T} {Q}{x}.\]

In scalar notation, used throughout most of this document, the objective function expressed as a QUBO is as follows:

\[\text{E}_{qubo}(a_i, b_{i,j}; q_i) = \sum_{i} a_i q_i + \sum_{i<j} b_{i,j} q_i q_j.\]

Note

Quadratic unconstrained binary optimization problems—QUBOs—are unconstrained in that there are no constraints on the variables other than those expressed in Q.

Graphs

A graph comprises a collection of nodes and edges, which can be used to represent an objective function’s variables and the connections between them, respectively.

For example, to represent a quadratic equation,

\[H(a,b) = 5a + 7ab - 3b,\]

you need two nodes, \(a\) and \(b\), with biases of \(5\) and \(-3\), and an edge between them with a strength of 7, as shown in Figure 10.

two variable objective function

Fig. 10 Two-variable objective function.

Minor Embedding

This graphic representation means you can map the objective function to the QPU:

  • Nodes that represent the objective function’s variables such as \(s_i\) (Ising) or \(q_i\) (QUBO) are mapped to qubits on the QPU.
  • Edges that represent the objective function’s quadratic coefficients such as \(J_{i,j}\) (Ising) and \(b_{i,j}\) (QUBO) are mapped to couplers.

The process of mapping variables in the problem formulation to qubits on the QPU is known as minor embedding.

The Constraints Example: Minor-Embedding chapter demonstrates minor embedding with an example; typically Ocean software handles it automatically.

Problem-Solving Process

In summary, to solve a problem on D-Wave solvers you formulate the problem as an objective function, usually in Ising or QUBO format. Low energy states of the objective function represent good solutions to the problem. Because you can represent the objective function as a graph, you can map it to the QPU:[3] linear coefficients to qubit biases and quadratic coefficients to coupler strengths. The QPU uses quantum annealing to seek the minimum of the resulting energy landscape, which corresponds to the solution of your problem.

[3]Classical solvers might not require minor-embedding and hybrid quantum-classical solvers might embed parts of the problem on the QPU while solving other parts with classical algorithms on CPUs or GPUs.