Definitions

Binary Quadratic Model

The binary quadratic model (BQM) class of problems consists of Ising models and quadratic unconstrained binary optimization (QUBO) models. These two forms are mathematically equivalent, and our software tools allow you to work in either domain. In this guide, we will provide examples and exercises in both forms. Note that some problems may see better results with Ising over QUBO, and vice versa.

A BQM takes the following form.

\[\min \left(\sum_i a_i v_i + \sum_i \sum_{j>i} b_{i,j} v_i v_j + c\right)\]

The coefficients \(a_i\) and \(b_{i,j}\) are constant numbers we choose to define our problem, as is the constant term \(c\). The binary variables \(v_i\) and \(v_j\) are the values that we are looking for to solve our problem. The best solution for these variables is the value for each \(v_i\) that produces the smallest value for the overall expression. Searching for the variables that minimize an expression is called an “argmin” in mathematics.

Let’s break this expression down.

Linear Terms:

The first summation, \(\sum a_i v_i\), contains linear terms, with each having just one binary variable.

Quadratic Terms:

The second summation, \(\sum \sum b_{i,j} v_i v_j\), contains quadratic terms, with each term in the summation containing a product of two variables.

Constants:

In the general BQM form we may or may not include constants. Since we are looking for an argmin, any constant terms will not affect our final answer. However, it may be useful when interpreting the output from D-Wave solvers and samplers.

Quadratic Unconstrained Binary Optimization

A QUBO model takes the following form.

\[\min \left(\sum_i a_i x_i + \sum_i \sum_{j>i} b_{i,j} x_i x_j + c\right)\]

The binary variables \(x_i\) and \(x_j\) may take values from \(\{0, 1\}\).

When we are ready to run a QUBO with the D-Wave Ocean software tool kit, one method is to store the QUBO in a matrix format for the Ocean SDK. We can map a QUBO to a matrix by placing linear terms along the diagonal and quadratic terms in the off-diagonal positions.

Example:

We can map \(x_1+2x_2+3x_3+12x_1 x_2+13x_1 x_3+14x_2 x_4\) to the following matrix.

\[\begin{split}\left[ \begin{array}{cccc} 1 & 12 & 13 & 0 \\ 0 & 2 & 0 & 14 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right]\end{split}\]

In this matrix, we place coefficient \(a_i\) in matrix position \((i,i)\) and coefficient \(b_{i,j}\) in matrix position \((i,j)\).

Exercise

Put the following QUBO into matrix form.

\[x_1+x_1x_2-3x_3+5\]

Ising Model

An Ising model takes the following form.

\[\min \left(\sum_i h_i s_i + \sum_i \sum_{j>i} J_{i,j} s_i s_j\right)\]

The binary variables \(s_i\) and \(s_j\) may take values from \(\{-1, +1\}\).

When it comes time to write Ocean programs, we will need to represent our Ising model as a matrix and a vector. We can map the quadratic terms of an Ising model to a matrix by placing them in the off-diagonal positions, and the linear terms to a vector as a list of coefficients as shown below.

Example:

We can map \(s_1+2s_2+3s_3+12s_1 s_2+13s_1 s_3+14s_2 s_4\) to the following list and matrix.

Linear

\[\begin{split}h = \left[ \begin{array}{cccc} 1 & 2 & 3 & 0 \\ \end{array} \right]\end{split}\]

Quadratic

\[\begin{split}J = \left[ \begin{array}{cccc} 0 & 12 & 13 & 0 \\ 0 & 0 & 0 & 14 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right]\end{split}\]

In this matrix, coefficient \(J_{i,j}\) in matrix position \((i,j)\).

Exercise

Put the following Ising model into matrix form.

\[s_1+s_1s_2-3s_3+5\]

Equivalence of QUBO and Ising

The Ising and QUBO models are mathematically equivalent — we can translate from one model to the other using a simple substitution.

QUBO to Ising

To translate a QUBO model to an Ising model, we use the following substitution.

\[x_i \mapsto \frac{s_i +1}{2}\]

Example

\[\begin{split}\begin{array}{rcl} f(x)&=&-22x_1-6x_2-14x_3 + 20x_1x_2+28s_1s_3+9\\ &=&-22\left(\frac{s_1+1}{2}\right)-6\left(\frac{s_2+1}{2}\right)-14\left(\frac{s_3+1}{2}\right) + 20\left(\frac{s_1+1}{2}\right)\left(\frac{s_2+1}{2}\right)+28\left(\frac{s_1+1}{2}\right)\left(\frac{s_3+1}{2}\right)+9\\ &=&-11s_1-11-3s_2-3-7s_3-7+5s_1x_2+5s_1+5s_2+5+7s_1x_3\\ & &+7s_1+7s_3+7+9\\ &=&s_1+2s_2+5s_1s_2+7s_1s_3 \end{array}\end{split}\]

Ising to QUBO

To translate an Ising model to a QUBO model, we use the following substitution.

\[s_i \mapsto 2x_i -1\]

Example

\[\begin{split}\begin{array}{rcl} g(x)&=&s_1+2s_2+5s_1x_2+7s_1s_3\\ &=&(2x_1-1)+2(2x_2-1)+5(2x_1-1)(2x_2-1)+7(2x_1-1)(2x_3-1)\\ &=&2x_1-1+4x_2-2+20x_1x_2-10x_1-10x_2+5+28x_1x_3-14x_1-14x_3+7\\ &=&-22x_1-6x_2-14x_3+20x_1x_2+28x_1x_3+9 \end{array}\end{split}\]

Exercise

Convert the following QUBO model to an Ising model.

\[x_1+x_1x_2-3x_3+5\]

Convert the following Ising model to a QUBO model.

\[s_1+s_1s_2-3s_3+5\]

Summary of Key Points

  • A BQM can contain constant, linear, and quadratic terms, and no higher-order terms.
  • We define the coefficients and constant in the expression.
  • The solution is the value of each binary variable that minimizes the expression.