Quadratic Unconstrained Binary Optimization (QUBO)

Quadratic Unconstrained Binary Optimization (QUBO) consists in, given a real symmetric matrix \(Q\), minimizing the following cost function \(q\):

\[q(x_{1},...,x_{n}) = \sum_{i,j=1}^{n} - Q_{ij}x_{i}x_{j}\]

where \(x_{1},...,x_{n}\in \{0,1\}\) are binary variables.

Written differently, by solving a QUBO problem, we mean solving, given \(Q\):

\[\min_{x_{1}...x_{n}\in \{0,1\}} \sum_{i,j=1}^{n} - Q_{ij}x_{i}x_{j}\]

Note

The diagonal of \(Q\) is allowed to contain non-zero elements. Because \(\forall i \quad x_{i}\in\{0,1\}\), \(x_{i}^{2} = x_{i}\), and the diagonal terms in the sum above effectively correspond to a linear part of the cost function, which can be seen as similar to the magnetic field terms in Ising Hamiltonians.

QUBO instances are in one-to-one correspondance with Ising Hamiltonians and cost functions.

Indeed, starting from the expression above for \(q\), the QUBO cost function, and defining \(s_{i}=2x_{i}-1\) (\(\in \{-1,1\}\) as \(x_{i}\in\{0,1\}\)), i.e \(x_{i}=\frac{s_{i}+1}{2}\), one can indeed write:

\[\begin{split}q(x_{1},...x_{n}) &= \sum_{i,j=1}^{n} - Q_{i,j} x_{i}x_{j} \\~\\ &= - \sum_{i,j=1}^{n} Q_{i,j} \left(\frac{s_{i}+1}{2}\right)\left(\frac{s_{j}+1}{2}\right) \\~\\ &= - \sum_{i,j=1}^{n} \frac{Q_{i,j}}{4}\left(1+s_{i}+s_{j}+s_{i}s_{j}\right) \\~\\ &= - \sum_{i,j=1}^{n} \frac{Q_{i,j}}{4} - \sum_{i}\left(\sum_{j}\frac{Q_{i,j}}{4}\right) s_{i} - \sum_{j}\left(\sum_{i}\frac{Q_{i,j}}{4}\right) s_{j} - \sum_{i,j=1}^{n} \frac{Q_{i,j}}{4} s_{i}s_{j} \\~\\ &= - \sum_{i,j=1}^{n} \frac{Q_{i,j}}{4} - \sum_{i=1}^{n} \frac{Q_{i,i}}{4} - \sum_{i}\left(\sum_{j}\frac{Q_{i,j}}{2}\right) s_{i} - \sum_{i,j | i\neq j}^{n} \frac{Q_{i,j}}{4} s_{i}s_{j} \\~\\ &= - \sum_{i=1}^{n} h_{i}s_{i} - \sum_{i,j=1}^{n} J_{ij}s_{i}s_{j} + o\end{split}\]

with \(h_{i}=\sum_{j}\frac{Q_{i,j}}{2}\), \(J_{ij}=\frac{Q_{i,j}}{4}\) and an offset term \(o=- \sum_{i,j=1}^{n} \frac{Q_{i,j}}{4} - \sum_{i=1}^{n} \frac{Q_{i,i}}{4}\).

To produce such QUBO-formulated problems, one can use the qat.opt.QUBO class:

import numpy as np
from qat.opt import QUBO
from qat.core.variables import Variable

problem_size = 5  # number of qubits for annealing, can reach to 100s even 1000s

# Q matrix
np.random.seed(248)
any_mat = np.random.rand(problem_size, problem_size)
q_mat = (any_mat + np.transpose(any_mat)) / 2  # make it symmetric

# Offset - can be 0
offset = 3.52

# Create a QUBO problem
problem_QUBO = QUBO(Q=q_mat,
                    offset_q=offset)

print("Q matrix:")
print(problem_QUBO.q_matrix)

# Create a job by specifying the gamma function (needed for SQA)
t_var = Variable("t")
tmax = 1.23
gamma_max = 170.89 # it is usually problem-specific
gamma_t_fun = gamma_max * (1 - t_var / tmax)  # linear decrease to 0 at t=tmax
problem_QUBO_job = problem_QUBO.to_job("sqa", gamma_t=gamma_t_fun, tmax=tmax)
print("\nA QUBO Job has been created - ready to run on an annealing QPU.")

# Create an Ising Observable from the QUBO problem
problem_QUBO_Ising_obs = problem_QUBO.get_observable("ising")
print("An Ising Observable has also been created - to be fed in a Schedule (together with gamma_t) from which a Job can also be produced.")

Q matrix:
[[0.69198662 0.73860143 0.23485743 0.65543516 0.74898502]
 [0.73860143 0.19440743 0.55240091 0.42782353 0.46931252]
 [0.23485743 0.55240091 0.9406734  0.5541593  0.73200663]
 [0.65543516 0.42782353 0.5541593  0.65215284 0.63773675]
 [0.74898502 0.46931252 0.73200663 0.63773675 0.28187286]]

A QUBO Job has been created - ready to run on an annealing QPU.
An Ising Observable has also been created - to be fed in a Schedule (together with gamma_t) from which a Job can also be produced.

A QUBO problem can be translated to Ising and CombinatorialProblem via the to_ising() and to_combinatorial_problem() methods, respectively.

QUBO problems can be further converted to both ising Observables and terms Observables, the second being used for gate-based or analog quantum computations.