QUBO: Quadratic Unconstrained Binary Optimization

QUBO is the standard mathematical form for optimization problems on quantum annealers. It underpins D-Wave's Advantage system, QAOA on gate-based hardware, and a wide class of combinatorial optimization problems in logistics, finance, and operations research.

Quantum field lines representing the energy landscape optimised by QUBO solvers

What is a QUBO?

A QUBO is an optimization problem over binary variables where the objective function is at most quadratic, meaning it contains terms involving at most two variables multiplied together. The standard form is:

minimize: x^T Q x

where x is a vector of binary variables (each x_i in {0, 1}) and Q is an upper-triangular matrix of real coefficients.

The diagonal entries Q_ii represent linear terms (coefficients on individual variables). The off-diagonal entries Q_ij represent quadratic terms (coefficients on products x_i * x_j). The goal is to find the binary assignment that minimizes this expression.

Despite the "unconstrained" in the name, QUBO can represent constrained problems. Constraints are encoded as penalty terms added to the objective, expressions that are zero when the constraint is satisfied and positive when violated, scaled by a penalty coefficient large enough to make violations suboptimal.

QUBO, Ising model, and quantum hardware

Quantum annealers like D-Wave's Advantage system natively implement the Ising model: a network of spins (each +1 or -1) connected by couplings, evolving toward a low-energy configuration. QUBO and the Ising model are mathematically equivalent, you can convert between them by substituting x_i = (s_i + 1) / 2.

QUBO

  • Variables: binary, x_i in {0, 1}
  • Objective: minimize x^T Q x
  • Common in: optimization literature, Ocean SDK
  • Constraints: encoded as penalty terms

Ising model

  • Variables: spins, s_i in {+1, -1}
  • Objective: minimize -sum(J_ij s_i s_j) - sum(h_i s_i)
  • Common in: physics literature, hardware APIs
  • Direct mapping to D-Wave qubit couplings

D-Wave's Ocean SDK accepts both forms. The BinaryQuadraticModel (BQM) class handles QUBO natively and converts to Ising automatically for hardware submission. QAOA on gate-based hardware also uses the Ising Hamiltonian internally, making QUBO a relevant formulation for both annealing and gate-based quantum optimization.

Problems that map to QUBO

Graph problems

Maximum cut (MaxCut), graph coloring, minimum vertex cover, and graph partitioning all have well-known QUBO formulations. MaxCut in particular is a benchmark problem for QAOA on gate-based hardware and for D-Wave annealing.

Logistics and routing

Vehicle routing, job shop scheduling, bin packing, and supply chain optimization can be formulated as QUBOs. These are among the most commercially active areas for quantum optimization.

Finance

Portfolio optimization, selecting assets to maximize return subject to risk and budget constraints, maps naturally to QUBO when asset inclusion is treated as a binary decision. Quantum finance is one of the most active application areas.

Machine learning

Training binary classifiers, clustering with binary cluster assignments, and feature selection can be expressed as QUBOs. Quantum annealing has been applied to support vector machine training and to Boltzmann machine learning.

Courses covering QUBO and quantum optimization

Learn QUBO formulation, the Ising model, D-Wave programming, and QAOA.

QUBO and optimization tutorials

Frequently asked questions

What is QUBO?
QUBO stands for Quadratic Unconstrained Binary Optimization. It is the standard mathematical form for expressing optimization problems on quantum annealers like D-Wave's Advantage system. In a QUBO, you have binary variables (0 or 1), an objective function that is at most quadratic in those variables, and no explicit constraints, constraints are encoded as penalty terms added to the objective. Solving a QUBO means finding the assignment of binary variables that minimizes the objective function.
What is the relationship between QUBO and the Ising model?
QUBO and the Ising model are mathematically equivalent, you can convert between them with a linear substitution. The Ising model uses spin variables (-1 or +1) instead of binary variables (0 or 1), and is the native form for quantum annealing hardware. D-Wave's Ocean SDK accepts both forms and handles the conversion internally. Most optimization literature uses QUBO; quantum hardware documentation often uses Ising. Understanding both is useful for reading papers and working with different tools.
What kinds of problems can be expressed as QUBOs?
Many combinatorial optimization problems have natural QUBO representations: graph partitioning, maximum cut (MaxCut), number partitioning, vehicle routing, job scheduling, portfolio optimization, traffic flow optimization, supply chain logistics, and protein folding. The key requirement is that the problem can be expressed with binary decision variables and a quadratic objective. Constraints are added as penalty terms. Problems with continuous variables or high-degree polynomial objectives require reformulation.
Do I need a quantum computer to solve QUBOs?
No. QUBO is a mathematical formulation, not a hardware requirement. Classical solvers (simulated annealing, tabu search, branch-and-bound) can solve QUBOs, and for small instances they are often faster than quantum hardware. D-Wave's hybrid solvers combine quantum annealing with classical heuristics and are competitive on larger instances. You can develop and test QUBO formulations locally using D-Wave's Ocean SDK simulators before running on real hardware.
How do you encode constraints in a QUBO?
Constraints are encoded as penalty terms: mathematical expressions that add a large positive value to the objective whenever a constraint is violated. For example, the constraint x1 + x2 = 1 (exactly one of two binary variables must be 1) becomes the penalty term P * (x1 + x2 - 1)^2, where P is a penalty coefficient large enough to make constraint violations suboptimal. D-Wave's Ocean SDK provides utilities like Constraints and add_constraint() to handle this automatically for common constraint types.