Quadratic unconstrained binary optimization (QUBO) is a class of mathematical optimization problems in which a quadratic objective is minimized over variables restricted to or , with no additional explicit constraints. Despite its simple form, QUBO can represent many problems in scheduling, resource allocation, graph optimization, and statistical modeling. It is closely related to integer programming and is mathematically equivalent, through a change of variables, to finding a minimum-energy configuration of an Ising model with pairwise interactions.
Mathematical formulation
A QUBO problem can be written as
where , , and are real coefficients. The constant changes the objective value but not the minimizing assignments.
The variables usually encode yes-or-no decisions: whether an item is selected, a task occupies a time slot, or a vertex belongs to a particular group. Linear terms assign individual costs or rewards, while pairwise terms describe interactions between decisions. In a minimization problem, a positive penalizes simultaneously setting ; a negative coefficient rewards that joint choice, although the full objective determines which assignments are optimal.
An equivalent matrix formulation is
Because binary variables satisfy , linear terms can be placed on the diagonal of . Two conventions are common:
- Upper-triangular convention: , for , and for .
- Symmetric convention: and for .
Failing to distinguish these conventions can introduce a factor-of-two error in interaction coefficients. For an arbitrary real matrix, only its symmetric part contributes to the quadratic form, since
“Unconstrained” does not mean that the variables are unrestricted: the binary domain remains essential. It means that there are no explicit constraints beyond that domain.
Relation to pseudo-Boolean optimization
A pseudo-Boolean function maps binary vectors to real values. Every such function has a unique multilinear polynomial representation on . QUBO is the case in which that representation has degree at most two.
The restriction to quadratic degree is substantial, but auxiliary binary variables can be used to convert higher-degree objectives into quadratic ones. For example, a product can be represented by a new binary variable , with consistency enforced by the penalty
For binary arguments, exactly when , and otherwise. A cubic term can therefore be replaced by , together with a sufficiently strong multiple of .
This process, called quadratization, can increase both the number of variables and the required coefficient magnitudes. Its usefulness depends on the resulting formulation, not merely on the existence of a reduction.
Encoding constraints as penalties
Many applications begin with a constrained problem rather than a QUBO. Constraints can sometimes be moved into the objective function as penalties:
where for feasible assignments and for infeasible ones. The coefficient must be large enough that violating a constraint cannot produce a better objective value.
Linear equalities
A linear equality
can be enforced with
Expansion produces only linear and quadratic terms because .
A common example is an exactly-one constraint,
with penalty
This encoding is useful when a task must receive exactly one resource or an object must occupy exactly one position.
Inequalities and auxiliary variables
An integer-valued inequality can often be converted to an equality by introducing a nonnegative integer slack variable. A bounded slack variable can then be encoded using binary variables before applying a squared penalty.
Not every constraint requires slack variables. For example, the prohibition against selecting both and can be enforced directly by a term . Choosing an encoding involves trade-offs among variable count, interaction density, and coefficient range.
Penalty strength
Let
be the range of the original objective over all binary assignments. Suppose the feasible set is nonempty and the penalty is at least on every infeasible assignment. Then
is a sufficient condition for every global minimizer of to be feasible.
This bound is often conservative. If is too small, the encoded optimum may violate the intended constraints. If it is unnecessarily large, the objective can become dominated by penalty terms, making relevant cost differences harder for numerical solvers or finite-precision hardware to distinguish. Moreover, even a correctly chosen penalty guarantees feasibility only for global optima; a heuristic can still return an infeasible assignment.
Equivalence to the Ising model
Introduce spin variables through
Substitution gives
where
and
Thus QUBO and Ising energy minimization have corresponding configurations and objective values up to an additive constant. Sign conventions vary: some descriptions of the Ising model place an overall minus sign before the interaction or field terms.
The equivalence explains why QUBO is used in quantum annealing and other Ising-based optimization systems. It also allows methods developed for statistical physics to be applied to binary optimization. The equivalence is mathematical; by itself, it implies neither an efficient algorithm nor a quantum computational advantage.
Example: maximum cut
The maximum-cut problem provides a direct QUBO formulation without auxiliary variables. Let an undirected graph have edge weights , and let indicate the side of a partition containing vertex .
An edge crosses the partition exactly when its endpoint variables differ. Its cut indicator is
The total cut weight is therefore
Maximizing is equivalent to minimizing the QUBO
Complementing every bit leaves the cut unchanged, so assignments and represent the same partition with its two sides exchanged. Such symmetries can sometimes be removed by fixing one variable.
Computational complexity and special cases
General QUBO is NP-hard, as follows, for example, from its ability to express maximum cut. With rational coefficients represented in binary, the decision problem of whether an assignment has objective value at most a given rational threshold is NP-complete.
An exhaustive search examines assignments. Practical algorithms may perform much better on particular instances, but no polynomial-time algorithm is known for arbitrary QUBO.
The interaction graph has one vertex per variable and an edge wherever . Its structure is often more informative than variable count alone:
- If there are no interactions, each variable can be optimized independently.
- Disconnected components can be solved separately.
- Graphs with bounded treewidth admit dynamic-programming methods whose exponential dependence is confined to the width rather than the total number of variables.
- A submodular quadratic objective, characterized in this representation by for every pair, can be minimized using a suitable minimum-cut construction.
Discrete difficulty should not be inferred solely from whether a displayed coefficient matrix is positive semidefinite. Since on the binary domain, adding
leaves every binary objective value unchanged while modifying the curvature of its continuous extension. In particular, a convex continuous extension does not remove the difficulty imposed by binary decisions.
Solution methods
Exact algorithms
Exact methods include enumeration, branch and bound, cutting-plane methods, and algorithms based on graph structure. They seek a global optimum and can, when completed, provide a certificate of optimality.
A QUBO can also be converted into a mixed-integer linear formulation. For each quadratic product, introduce and impose
When and are binary, these inequalities enforce the product relation even if is continuous. The objective then becomes linear, allowing mixed-integer linear programming techniques to be used.
Heuristic methods
Common heuristics include local search, tabu search, simulated annealing, population-based search, and hybrid decomposition methods. They seek good assignments without generally proving global optimality.
For the coefficient representation above, flipping variable changes the objective by
This expression supports efficient incremental evaluation of candidate moves. A state for which no single flip improves the objective is a one-flip local minimum, but several coordinated flips may still improve it.
Relaxations and specialized hardware
Continuous relaxations replace binary restrictions with a larger domain and provide bounds or guidance for search. Approaches include linear, convex quadratic, and semidefinite programming relaxations.
Quantum annealers and other specialized devices attempt to find low-energy states of an encoded model. Limited connectivity may require additional physical variables to represent a single logical variable or interaction structure. Coefficient precision, noise, embedding overhead, and postprocessing can all affect the result.
Consequently, optimization performance is evaluated using solution quality, feasibility, runtime, success probability, and any available bounds—not simply whether a device accepts a QUBO input.
Development and applications
QUBO developed from classical work on zero–one quadratic programming and discrete optimization. Connections with spin systems and energy-based neural networks broadened its use, while quantum annealing increased interest in QUBO as a shared input format for optimization hardware.
Representative applications include:
- Scheduling and assignment: binary indicators encode allocation choices, with penalties enforcing exclusivity and capacity conditions.
- Graph optimization: cuts, independent sets, cliques, and coloring can be expressed directly or through penalties.
- Routing: formulations of the traveling salesman problem often use variables indicating which city occupies each tour position.
- Machine learning: feature selection, clustering, and some discrete model-selection tasks admit quadratic binary formulations.
- Portfolio selection: binary decisions represent inclusion or discrete allocation choices, while quadratic terms can express pairwise contributions derived from a covariance matrix.
A QUBO representation is not necessarily the most compact or effective formulation of an application. Penalties may create dense interaction graphs, integer encodings may add many variables, and quadratization may enlarge coefficient ranges. Comparisons with alternative formulations therefore depend on the complete modeling and solution process, including construction, embedding where applicable, feasibility checking, and verification of solution quality.