Quadratic unconstrained binary optimization (QUBO), also known as unconstrained binary quadratic programming (UBQP), is a combinatorial optimization problem with a wide range of applications from finance and economics to machine learning.
[1] QUBO is an NP hard problem, and for many classical problems from theoretical computer science, like maximum cut, graph coloring and the partition problem, embeddings into QUBO have been formulated.
[2][3] Embeddings for machine learning models include support-vector machines, clustering and probabilistic graphical models.
[4] Moreover, due to its close connection to Ising models, QUBO constitutes a central problem class for adiabatic quantum computation, where it is solved through a physical process called quantum annealing.
[5] The set of binary vectors of a fixed length
We are given a real-valued upper triangular matrix
define a weight for each pair of indices
that assigns a value to each binary vector through Intuitively, the weight
The QUBO problem consists of finding a binary vector
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
QUBO is scale invariant for positive factors
unchanged: In its general form, QUBO is NP-hard and cannot be solved efficiently by any polynomial-time algorithm.
has certain properties,[7] for example: 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.
can also be relaxed to continuous variables within the bounds zero and one.
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.
Here, we are given a set of 20 points in 2D space, described by a matrix
For two clusters, we can assign a binary variable
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.
denote the Euclidean distance between points
In order to define a cost function to minimize, when points
are in the same cluster we add their positive distance
The cost function thus comes down to From the second line, the QUBO parameters can be easily found by re-arranging to be: Using these parameters, the optimal QUBO solution will correspond to an optimal cluster w.r.t.
QUBO is very closely related and computationally equivalent to the Ising model, whose Hamiltonian function is defined as with real-valued parameters
yields an equivalent QUBO problem:[2] where and using the fact that for a binary variable
, it can be neglected during optimization and is only important for recovering the original Hamiltonian function value.
This artificial intelligence-related article is a stub.