Problem Formulation: Key Concepts

This section introduces some key concepts you must understand before you can formulate a problem for the D-Wave QPU: objective functions, Ising model, quadratic unconstrained binary optimization problems (QUBOs), and graphs.

Objective Functions

To understand how to express a problem in a form that the D-Wave system can solve, we must first develop an objective function, which is a mathematical expression of the energy of a system as a function of binary variables representing the qubits. In most cases, 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.

Energy of objective function.

Fig. 9 Energy of objective function.

Consider quadratic functions, which have one or two variables per term:

\begin{equation} D = Ax + By + Cxy \end{equation}

where \(A\), \(B\), and \(C\) are constants. Single variable terms—\(Ax\) and \(By\), for example—are linear and act to bias the variable. Two-variable terms—\(Cxy\), for example—are quadratic with a relationship between the variables.

Problem Formulations: Ising and QUBO

Two formulations we look at for objective functions are found in the Ising model and in QUBO problems. Conversion between these two formulations is trivial.

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:

\begin{equation} \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 \end{equation}

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. Variables are TRUE and FALSE, states that correspond to 1 and 0 values.

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

\begin{equation} f(x) = \sum_{i} {Q_{i,i}}{x_i} + \sum_{i<j} {Q_{i,j}}{x_i}{x_j} \end{equation}

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

This can be expressed more concisely as

\begin{equation} \min_{{x} \in {\{0,1\}^n}} {x}^{T} {Q}{x}. \end{equation}

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

\begin{equation} \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. \end{equation}

Note

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

Notation Comparison

The transformation between Ising and QUBO is

\begin{equation} s = q2 - 1. \end{equation}

Figure 10 compares Ising and QUBO notation and related terminology.

Notation comparison.

Fig. 10 Notation conventions.

Graphs

Objective functions can be represented by graphs. A graph comprises a collection of nodes (representing variables) and the connections between them (edges).

For example, to represent two variables in a quadratic equation,

\begin{equation} H(a,b) = 5a + 7ab - 3b, \end{equation}

we need two nodes, \(a\) and \(b\), with biases of \(5\) and \(-3\) and a connection between them with a strength of 7; see Figure 11.

two variable objective function

Fig. 11 Two-variable objective function.

On the D-Wave system, a node is a qubit and an edge is a coupler.