Mapping Optimization Problems to Quadratic Unconstrained Binary Optimization

207 concepts148 papers2 proposals

Traditional optimization algorithms rely on step-by-step logical branching, linear programming relaxations, or gradient descent. However, emerging hardware platforms—such as quantum annealers, neutral-atom processors, and classical Coherent Ising Machines—operate on an entirely different paradigm. They do not execute sequential instructions; instead, they evolve physically toward a state of minimum energy.

To leverage this physics-based computation, we must translate discrete combinatorial problems into a universal mathematical language that mirrors physical energy landscapes. This language is Quadratic Unconstrained Binary Optimization (QUBO).

The Anatomy of a QUBO Mapping

A QUBO problem seeks to minimize an energy function constructed from a vector of binary variables $x_i \in \{0, 1\}$:

$$E(x) = \sum_{i} c_i x_i + \sum_{i < j} Q_{ij} x_i x_j$$

This specific form is powerful because it maps perfectly to the Ising model in physics, where binary variables represent magnetic spins (up or down) and $Q_{ij}$ represents the physical coupling forces between them.

To encode a real-world problem into this format, an optimization task must undergo two core transformations:

  1. Objective Encoding: The primary goal (e.g., minimizing distance, maximizing coverage, or minimizing classification error) is expressed as a quadratic combination of binary choices.
  2. Constraint Relaxation via Penalties: Because QUBO is unconstrained, hard constraints (such as "choose exactly one route") cannot be enforced by traditional boundaries. Instead, they are added directly to the objective function as squared penalty terms that increase the system's energy if violated.

Intuition: Turning Constraints into Algebra

Consider a simple constraint where we must choose exactly one of two options, meaning $x_1 + x_2 = 1$. To enforce this in an unconstrained system, we minimize the squared violation:

$$P = \gamma (x_1 + x_2 - 1)^2$$

where $\gamma$ is a positive scalar penalty weight. Expanding this algebraic expression yields:

$$P = \gamma (x_1^2 + x_2^2 + 1 + 2x_1x_2 - 2x_1 - 2x_2)$$

Because $x_i$ is binary, $x_i^2 = x_i$. We can substitute this identity to simplify the expression into a strictly linear and quadratic form:

$$P = \gamma (1 - x_1 - x_2 + 2x_1x_2)$$

By dropping the constant $1$ (which does not change the location of the minimum), we can inject these linear coefficients and the pairwise interaction coefficient ($2\gamma x_1x_2$) directly into our QUBO matrix. When the physical hardware minimizes the overall energy, it naturally avoids states where $P > 0$, effectively satisfying the constraint through energy minimization.

Overcoming Hardware Limitations: Degree Reduction

Real-world problems often involve complex, multi-variable interactions where three or more variables interact simultaneously (Higher-Order Unconstrained Binary Optimization, or HUBO). Physical hardware, however, typically only supports pairwise interactions ($Q_{ij}$).

To bridge this gap, researchers use degree reduction. As explained by Krzysztof Domino et al. in the context of railway rescheduling in Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing, higher-order polynomial terms can be systematically decomposed into quadratic forms by introducing auxiliary "slack" variables. For example, a cubic term $x_1 x_2 x_3$ can be reduced to a quadratic term by introducing a new binary variable $y = x_1 x_2$, enforced by an accompanying penalty function. This reduction process ensures that high-dimensional logical structures can fit within the pairwise interaction constraints of physical quantum annealing chips.

Applications Across Domains

The power of QUBO mapping lies in its universality. By changing the coefficients in the $Q$ matrix, the exact same physical hardware can solve completely different problems across unrelated fields.

Resource Allocation and Scheduling

In telecommunications, managing shared radio frequencies is a major bottleneck. Kazuhiro Saito et al. demonstrated in Evaluating dynamic spectrum allocation using quantum annealing that formulating dynamic spectrum allocation as a QUBO model allows quantum-inspired classical solvers to achieve massive speedups and higher allocation accuracy over traditional industry solvers by treating conflicting objectives as a single energy function.

Computer Vision and Geometric Fitting

Geometric alignment and tracking problems are inherently combinatorial. Vladislav Golyanik in A Quantum Computational Approach to Correspondence Problems on Point Sets proposed a QUBO formulation for point set registration, mapping spatial alignment parameters directly to the ground state of a problem Hamiltonian.

Similarly, Matteo Farina et al. tackled multi-model geometric fitting in Quantum Multi-Model Fitting. By mapping the problem to a disjoint set cover task within a QUBO framework, the authors enabled adiabatic quantum computers to segment motion in real-world video datasets without requiring continuous relaxations.

Machine Learning and Matrix Factorization

QUBO mappings also extend directly to machine learning workflows. Xi-Jun Yuan et al. showed in Quantum support vector machines for aerodynamic classification how the standard quadratic programming formulation of a Support Vector Machine (SVM) can be converted into a QUBO format, allowing classification tasks to be executed on quantum annealing hardware.

For unsupervised learning, Cesar Ojeda et al. demonstrated in Adiabatic Quantum Computing for Kernel k=2 Means Clustering how to map kernel clustering onto an Ising model by representing cluster assignments as bipolar variables. Furthermore, Daniel O’Malley et al. in Nonnegative/Binary matrix factorization with a D-Wave quantum annealer utilized a hybrid quantum-classical approach to decompose binary matrices, proving that casting discrete feature extraction sub-problems as QUBOs allows specialized hardware to find high-quality solutions in the sub-millisecond regime.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_unconstrained_binary_optimizat_c4a02d0f,
  title = {quadratic unconstrained binary optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-unconstrained-binary-optimization/rdr_c4a02d0f0f284673baef33d960169d92},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_unconstrained_binary_optimizat_c4a02d0f_v1,
  title = {quadratic unconstrained binary optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-unconstrained-binary-optimization/rdr_c4a02d0f0f284673baef33d960169d92/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake