Quadratic Unconstrained Binary Optimization (QUBO)
Quadratic Unconstrained Binary Optimization (QUBO) consists in, given a real symmetric matrix \(Q\), minimizing the following cost function \(q\):
where \(x_{1},...,x_{n}\in \{0,1\}\) are binary variables.
Written differently, by solving a QUBO problem, we mean solving, given \(Q\):
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:
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
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
problem_QUBO_job = problem_QUBO.to_job("sqa")
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 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 from which a Job can also be produced.
<stdin>:22: UserWarning: If SQAQPU is used, gamma_t will be needed.
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.