Definition
Let
the set of binary digits (or bits), then
is the set of binary vectors of fixed length
. Given a symmetric or upper triangular matrix
, whose entries
define a weight for each pair of indices
, we can define the function
that assigns a value to each binary vector
through

Alternatively, the linear and quadratic parts can be separated as

where
and
. This is equivalent to the previous definition through
using the diag operator, exploiting that
for all binary values
.
Intuitively, the weight
is added if both
and
. The QUBO problem consists of finding a binary vector
that minimizes
, i.e.,
.
In general,
is not unique, meaning there may be a set of minimizing vectors with equal value w.r.t.
. The complexity of QUBO arises from the number of candidate binary vectors to be evaluated, as
grows exponentially in
.
Sometimes, QUBO is defined as the problem of maximizing
, which is equivalent to minimizing
.
Properties
QUBO is scale invariant for positive factors
, which leave the optimum
unchanged:
.
In its general form, QUBO is NP-hard and cannot be solved efficiently by any polynomial-time algorithm. [6] However, there are polynomially-solvable special cases, where
has certain properties, [7] for example:
- If all coefficients are positive, the optimum is trivially
. Similarly, if all coefficients are negative, the optimum is
. - If
is diagonal, the bits can be optimized independently, and the problem is solvable in
. The optimal variable assignments are simply
if
, and
otherwise. - If all off-diagonal elements of
are non-positive, the corresponding QUBO problem is solvable in polynomial time. [8]
QUBO can be solved using integer linear programming solvers like CPLEX or Gurobi Optimizer. This is possible since QUBO can be reformulated as a linear constrained binary optimization problem. To achieve this, substitute the product
by an additional binary variable
and add the constraints
,
and
. Note that
can also be relaxed to continuous variables within the bounds zero and one.
Applications
QUBO is a structurally simple, yet computationally hard optimization problem. It can be used to encode a wide range of optimization problems from various scientific areas. [9]
Maximum Cut
Given a graph
with vertex set
and edges
, the maximum cut (max-cut) problem consists of finding two subsets
with
, such that the number of edges between
and
is maximized.
The more general weighted max-cut problem assumes edge weights
, with
, and asks for a partition
that maximizes the sum of edge weights between
and
, i.e.,

By setting
for all
this becomes equivalent to the original max-cut problem above, which is why we focus on this more general form in the following.
For every vertex in
we introduce a binary variable
with the meaning
if
and
if
. As
and
partition
, every
is in exactly one set, meaning there is a 1:1 correspondence between binary vectors
and partitions of
into two subsets.
We observe that, for any
, the expression
evaluates to 1 if and only if
and
are in different subsets. Let
with
. By using above expression we find that

is the sum of weights of all edges between
and
, where
. As this function is quadratic in
, it is a QUBO problem whose parameter matrix we can read from above expression as

after flipping the sign to make it a minimization problem.
Cluster Analysis
A bad cluster assignment.
A good cluster assignment.
Visual representation of a clustering problem with 20 points: Circles of the same color belong to the same cluster. Each circle can be understood as a binary variable in the corresponding QUBO problem.
As an illustrative example of how QUBO can be used to encode an optimization problem, we consider the problem of cluster analysis. Here, we are given a set of
points in 2D space, described by a matrix
, where each row contains two cartesian coordinates. We want to assign each point to one of two classes or clusters, such that points in the same cluster are similar to each other. For two clusters, we can assign a binary variable
to the point corresponding to the
-th row in
, indicating whether it belongs to the first (
) or second cluster (
). Consequently, we have 20 binary variables, which form a binary vector
that corresponds to a cluster assignment of all points (see figure).
One way to derive a clustering is to consider the pairwise distances between points. Given a cluster assignment
, the expression
evaluates to 1 if points
and
are in the same cluster. Similarly,
indicates that they are in different clusters. Let
denote the Euclidean distance between the points
and
, i.e.,
,
where
is the
-th row of
.
In order to define a cost function to minimize, when points
and
are in the same cluster we add their positive distance
, and subtract it when they are in different clusters. This way, an optimal solution tends to place points which are far apart into different clusters, and points that are close into the same cluster.
Let
with
for all
. Given an assignment
, such a cost function is given by

where
.
From the second line we can see that this expression can be re-arranged to a QUBO problem by defining

and ignoring the constant term
. Using these parameters, a binary vector minimizing this QUBO instance
will correspond to an optimal cluster assignment w.r.t. above cost function.
Connection to Ising models
QUBO is very closely related and computationally equivalent to the Ising model, whose Hamiltonian function is defined as

with real-valued parameters
for all
. The spin variables
are binary with values from
instead of
. Note that this formulation is simplified, since, in a physics context,
are typically Pauli operators, which are complex-valued matrices of size
, whereas here we treat them as binary variables. Many formulations of the Ising model Hamiltonian further assume that the variables are arranged in a lattice, where only neighboring pairs of variables
can have non-zero coefficients; here, we simply assume that
if
and
are not neighbors.
Applying the identity
yields an equivalent QUBO problem [10]

whose weight matrix
is given by

again ignoring the constant term, which does not affect the minization. Using the identity
, a QUBO problem with matrix
can be converted to an equivalent Ising model using the same technique, yielding

and a constant offset of
. [10]