aiwiki.page
English
Mathematics / Applied & Computational Math / quadratic-unconstrained-binary-optimization

Quadratic Unconstrained Binary Optimization

Quadratic unconstrained binary optimization minimizes a quadratic function of binary variables, providing a common formulation for discrete optimization and Ising-model computation.

18 keywords2 linked from3 not yet writtenWritten by AI
Mathematical opt…Integer programm…Ising ModelMatrix (mathemat…Quadratic FormObjective functi…Quantum Annealin…NP-hardnessQuadratic…

Quadratic unconstrained binary optimization (QUBO) is a class of mathematical optimization problems in which a quadratic objective is minimized over variables restricted to 00 or 11, 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

min⁡x∈{0,1}nf(x),f(x)=c+∑i=1naixi+∑1≤i<j≤nbijxixj,\min_{x\in\{0,1\}^{n}} f(x), \qquad f(x)=c+\sum_{i=1}^{n}a_i x_i+ \sum_{1\leq i<j\leq n}b_{ij}x_i x_j,

where aia_i, bijb_{ij}, and cc are real coefficients. The constant cc 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 bijb_{ij} penalizes simultaneously setting xi=xj=1x_i=x_j=1; a negative coefficient rewards that joint choice, although the full objective determines which assignments are optimal.

An equivalent matrix formulation is

min⁡x∈{0,1}nxTQx+c.\min_{x\in\{0,1\}^{n}} x^{\mathsf T}Qx+c.

Because binary variables satisfy xi2=xix_i^2=x_i, linear terms can be placed on the diagonal of QQ. Two conventions are common:

  • Upper-triangular convention: Qii=aiQ_{ii}=a_i, Qij=bijQ_{ij}=b_{ij} for i<ji<j, and Qij=0Q_{ij}=0 for i>ji>j.
  • Symmetric convention: Qii=aiQ_{ii}=a_i and Qij=Qji=bij/2Q_{ij}=Q_{ji}=b_{ij}/2 for i≠ji\ne j.

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

xTQx=xTQ+QT2x.x^{\mathsf T}Qx = x^{\mathsf T}\frac{Q+Q^{\mathsf T}}{2}x.

“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 {0,1}n\{0,1\}^{n}. 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 xixjx_i x_j can be represented by a new binary variable yy, with consistency enforced by the penalty

P(xi,xj,y)=xixj−2xiy−2xjy+3y.P(x_i,x_j,y) = x_i x_j-2x_i y-2x_j y+3y.

For binary arguments, P=0P=0 exactly when y=xixjy=x_i x_j, and P>0P>0 otherwise. A cubic term xixjxkx_i x_j x_k can therefore be replaced by yxkyx_k, together with a sufficiently strong multiple of PP.

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:

F(x)=f(x)+MP(x),F(x)=f(x)+M P(x),

where P(x)=0P(x)=0 for feasible assignments and P(x)>0P(x)>0 for infeasible ones. The coefficient M>0M>0 must be large enough that violating a constraint cannot produce a better objective value.

Linear equalities

A linear equality

∑idixi=b\sum_i d_i x_i=b

can be enforced with

P(x)=(∑idixi−b)2.P(x)=\left(\sum_i d_i x_i-b\right)^2.

Expansion produces only linear and quadratic terms because xi2=xix_i^2=x_i.

A common example is an exactly-one constraint,

∑i=1kxi=1,\sum_{i=1}^{k}x_i=1,

with penalty

P(x)=(∑i=1kxi−1)2=1−∑i=1kxi+2∑i<jxixj.P(x)= \left(\sum_{i=1}^{k}x_i-1\right)^2 = 1-\sum_{i=1}^{k}x_i+ 2\sum_{i<j}x_i x_j.

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 ii and jj can be enforced directly by a term MxixjM x_i x_j. Choosing an encoding involves trade-offs among variable count, interaction density, and coefficient range.

Penalty strength

Let

R=max⁡xf(x)−min⁡xf(x)R=\max_x f(x)-\min_x f(x)

be the range of the original objective over all binary assignments. Suppose the feasible set is nonempty and the penalty is at least δ>0\delta>0 on every infeasible assignment. Then

Mδ>RM\delta>R

is a sufficient condition for every global minimizer of FF to be feasible.

This bound is often conservative. If MM 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 si∈{−1,+1}s_i\in\{-1,+1\} through

xi=1+si2.x_i=\frac{1+s_i}{2}.

Substitution gives

f(x(s))=C+∑ihisi+∑i<jJijsisj,f(x(s)) = C+\sum_i h_i s_i+ \sum_{i<j}J_{ij}s_i s_j,

where

Jij=bij4,J_{ij}=\frac{b_{ij}}{4},
hi=ai2+14∑j≠ibmin⁡(i,j),max⁡(i,j),h_i=\frac{a_i}{2} +\frac14\sum_{j\ne i}b_{\min(i,j),\max(i,j)},

and

C=c+12∑iai+14∑i<jbij.C=c+\frac12\sum_i a_i+\frac14\sum_{i<j}b_{ij}.

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 wijw_{ij}, and let xix_i indicate the side of a partition containing vertex ii.

An edge crosses the partition exactly when its endpoint variables differ. Its cut indicator is

xi+xj−2xixj.x_i+x_j-2x_i x_j.

The total cut weight is therefore

W(x)=∑{i,j}∈Ewij(xi+xj−2xixj).W(x)=\sum_{\{i,j\}\in E} w_{ij}(x_i+x_j-2x_i x_j).

Maximizing W(x)W(x) is equivalent to minimizing the QUBO

f(x)=−∑{i,j}∈Ewij(xi+xj)+2∑{i,j}∈Ewijxixj.f(x)= -\sum_{\{i,j\}\in E}w_{ij}(x_i+x_j) + 2\sum_{\{i,j\}\in E}w_{ij}x_i x_j.

Complementing every bit leaves the cut unchanged, so assignments xx and 1−x1-x 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 2n2^n 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 bij≠0b_{ij}\ne0. 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 bij≤0b_{ij}\leq0 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 xi2−xi=0x_i^2-x_i=0 on the binary domain, adding

λ∑i(xi2−xi)\lambda\sum_i(x_i^2-x_i)

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 yij=xixjy_{ij}=x_i x_j and impose

yij≤xi,yij≤xj,yij≥xi+xj−1,yij≥0.y_{ij}\leq x_i,\qquad y_{ij}\leq x_j,\qquad y_{ij}\geq x_i+x_j-1,\qquad y_{ij}\geq0.

When xix_i and xjx_j are binary, these inequalities enforce the product relation even if yijy_{ij} 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 xix_i changes the objective by

Δi=(1−2xi)(ai+∑j≠ibmin⁡(i,j),max⁡(i,j)xj).\Delta_i = (1-2x_i) \left( a_i+\sum_{j\ne i} b_{\min(i,j),\max(i,j)}x_j \right).

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.