QUBO

QUBO stands for Quadratic Unconstrained Binary Optimization. It denotes a class of optimization problems in which the decision variables x_i take binary values in {0,1}, and the objective is a quadratic function: minimize f(x) = x^T Q x, where Q is a real symmetric matrix. Because x_i^2 = x_i for binary variables, the diagonal entries contribute linear terms and the off-diagonal entries encode pairwise interactions. The problem is unconstrained in the sense that x is restricted only to binary values; constraints are typically incorporated by adding penalty terms to the objective, yielding a pure QUBO objective over binary variables.

QUBO and the Ising model are equivalent representations of the same optimization task. By mapping binary variables x_i in {0,1} to spin variables s_i in {−1, +1} via x_i = (s_i + 1)/2, one can transform between a QUBO objective and an Ising energy E(s) = ∑ h_i s_i + ∑ J_ij s_i s_j. This equivalence makes QUBO a universal encoding for many combinatorial problems.

QUBO is used to formulate a wide range of NP-hard problems, such as maximum cut, maximum independent set, graph coloring, scheduling, and portfolio optimization. It has become standard in quantum computing, particularly for quantum annealing hardware, but it is also solvable with classical methods including simulated annealing, other heuristics, and mixed-integer or quadratic programming solvers.

Solving a QUBO involves finding a binary vector x that minimizes x^T Q x. The problem size and difficulty grow with n, so practical approaches rely on heuristics, problem-specific reformulations, or specialized hardware to obtain good solutions.