# 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. 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. 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. Fig. 11 Two-variable objective function.

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