# 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.

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

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:

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

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

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

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¶

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,

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.

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