Quadratic Unconstrained Binary Optimization (QUBO)

Part of Womanium Quantum + AI 2024 program

Definition

Quadratic unconstrained binary optimization is an optimization technique where the problem to be optimized is described using a binary quadratic model.

Binary quadratic models are mathematical models used to describe problems based on their objectives and constraints. These models can be represented as function where the goal of the optimization is to minimize or maximize this function.

A binary quadratic model contains linear and quadratic terms and its objective function can be mathematically represented as:

f (x) = \sum_{i} a_{i} x_{i} + \sum_{i < j} b_{i} x_{i} x_{j}

The first part of the function represents the linear terms and the second part represent the quadratic terms.

When optimizing the objective function it's commonly set such that the function is minimized, however if we needed to maximize our function we can simply negate all of the coefficients then minimize it.

max f (x) = min (- f (x))

Matrix Representation

An objective function can be mapped such that it's represented as a matrix. The matrix can be constructed in an upper-triangular form or in a symmetric form.

A matrix of the objective function $f (x)$ can be constructed as:

Q = [\begin{matrix} a_{x_{1}} & a_{x_{1} x_{2}} & a_{x_{1} x_{3}} & \dots & a_{x_{1} x_{n}} \\ 0 & a_{x_{2}} & a_{x_{2} x_{3}} & \dots & a_{x_{2} x_{n}} \\ 0 & 0 & a_{x_{3}} & \dots & a_{x_{3} x_{n}} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & a_{x_{n}} \end{matrix}]

Where $a_{y}$ is the coefficient of the term $y$ .

Note

Note that all the coefficients of linear terms fall along the main diagonal of the matrix, while the coefficients of quadratic terms are in the upper-right section.

Now that we have the objective function represented as a matrix, we define $x$ as a vector for to be applied to the matrix.

$x = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}]$

Finally we define optimizing the objective function as:

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

\begin{aligned} x^{T} Q x & = [\begin{array}{c} x_{1} & x_{2} & \dots & x_{n} \end{array}] [\begin{array}{c} a_{x_{1}} & a_{x_{1} x_{2}} & \dots & a_{x_{1} x_{n}} \\ 0 & a_{x_{2}} & \dots & a_{x_{2} x_{n}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & a_{x_{n}} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{array}] \\ = [\begin{array}{c} a_{x_{1}} x_{1} & a_{x_{2}} x_{2} + a_{x_{1} x_{2}} x_{1} & \dots & x_{n} a_{x_{n}} + a_{x_{1} x_{n}} x_{1} + \dots + a_{x_{n - 1} x_{n}} x_{n - 1} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{array}] \\ = [\begin{array}{c} (a_{x_{1}} x_{1}^{2}) + (a_{x_{2}} x_{2}^{2} + a_{x_{1} x_{2}} x_{1} x_{2}) + \dots + (x_{n} a_{x_{n}}^{2} + a_{x_{1} x_{n}} x_{1} x_{n} + \dots + a_{x_{n - 1} x_{n}} x_{n - 1} x_{n}) \end{array}] \end{aligned}

But since $x$ is a vector of binary variables we know that:

x = {\begin{cases} 0 \\ 1 \end{cases} ⟹ x^{2} = {\begin{cases} 0^{2} = 0 \\ 1^{2} = 1 \end{cases} ⟹ x^{2} = x

\begin{aligned} ∴ [\begin{array}{c} (a_{x_{1}} x_{1}^{2}) + (a_{x_{2}} x_{2}^{2} + a_{x_{1} x_{2}} x_{1} x_{2}) + \dots + (x_{n} a_{x_{n}}^{2} + a_{x_{1} x_{n}} x_{1} x_{n} + \dots + a_{x_{n - 1} x_{n}} x_{n - 1} x_{n}) \end{array}] \\ = [\begin{array}{c} (a_{x_{1}} x_{1}) + (a_{x_{2}} x_{2} + a_{x_{1} x_{2}} x_{1} x_{2}) + \dots + (x_{n} a_{x_{n}} + a_{x_{1} x_{n}} x_{1} x_{n} + \dots + a_{x_{n - 1} x_{n}} x_{n - 1} x_{n}) \end{array}] \\ = [\begin{array}{c} \sum_{i} a_{x_{i}} x_{i} + \sum_{i < j} a_{x_{i} x_{j}} x_{i} x_{j} \end{array}] \end{aligned}

This proves that the matrix representation of the objective function is equivalent to the function representation.

Examples

Example 1

Find the values of each $x_{i}$ that will minimize the following function:

f (x) = 5 x_{1} + 7 x_{1} x_{2} - 3 x_{2}

We try all $2^{2}$ possible combinations of $x_{1}$ and $x_{2}$ to find the smallest value of $f (x)$ .

$x_{1} = 1, x_{2} = 0 \to f (x) = 5 * 0 + 7 * 0 * 0 - 3 * 0 = 0$
$x_{1} = 1, x_{2} = 0 \to f (x) = 5 * 1 + 7 * 1 * 0 - 3 * 0 = 5$
$x_{1} = 0, x_{2} = 1 \to f (x) = 5 * 0 + 7 * 0 * 1 - 3 * 1 = - 3$
$x_{1} = 1, x_{2} = 1 \to f (x) = 5 * 1 + 7 * 1 * 1 - 3 * 1 = 9$

$x_{1} = 0, x_{2} = 1$ minimizes the function and results in $- 3$ .

Example 2

Represent the following objective functions in a matrix form.

\begin{aligned} min f (x) & = 5 x_{1} + 7 x_{1} x_{2} - 3 x_{2} \\ \to Q = [\begin{array}{c} 5 & 7 \\ 0 & - 3 \end{array}] \end{aligned}

Solving a Quadratic Unconstrained Binary Optimization Problem

The simplest way to solve a QUBO problem is to iterate over all possible values of the vector ( x ) and compute the function result:

r e s u l t = x^{T} Q x

By keeping track of the vector that achieves the minimum result, we obtain the solution at the end.

This approach has a classical complexity of $O (2^{n})$ , where $n$ is the number of binary variables.

< Prev