BQMs

Binary Quadratic Models (BQMs) are a standard mathematical representation used to formulate and solve a wide range of combinatorial optimization problems. In a BQM, the decision variables are binary, x_i ∈ {0,1}, and the objective (or energy) function is quadratic in these variables: E(x) = ∑_i h_i x_i + ∑_{i<j} J_{ij} x_i x_j, where h_i are linear biases and J_{ij} are pairwise couplings. The goal is to find the variable assignment that minimizes (or maximizes) E(x).

BQMs are closely related to Ising models. By a simple variable transformation x_i = (s_i + 1)/2, the BQM can be reformulated as an Ising energy function in spins s_i ∈ {−1, 1}. This equivalence underpins the common use of BQMs in quadratic unconstrained binary optimization (QUBO) problems, which are widely used in both quantum and classical optimization contexts.

Applications of BQMs span many domains, including graph partitioning and clustering, maximum cut, facility location, scheduling, portfolio optimization, and various logistics problems. Many real-world problems are encoded as BQMs by selecting appropriate h_i and J_{ij} to capture linear costs and pairwise interactions.

Solving approaches include classical methods such as simulated annealing, branch-and-bound, and specialized solvers, as well as quantum-inspired and quantum annealing techniques. When implemented on quantum hardware, BQMs must be embedded into the device’s native graph, often requiring chains of physical qubits to represent a single logical variable; chain strength and calibration are important considerations.

Limitations include embedding overhead, precision and noise in coefficients, and the potential for multiple near-optimal solutions. BQMs provide a versatile framework for modeling and solving a broad class of optimization problems.