The promise of adiabatic quantum computing and quantum annealing is elegant: to solve an NP-hard combinatorial optimization problem, you map its cost function to an Ising spin glass or a Quadratic Unconstrained Binary Optimization (QUBO) problem. By initializing the system in a simple quantum superposition and slowly evolving it, the hardware naturally settles into the lowest-energy state—the global optimum of your problem.
In an ideal world, if your problem has $N$ variables with arbitrary interactions, you would map it directly to $N$ fully connected physical qubits. In reality, physical quantum processors have sparse, rigid hardware topologies. This mismatch between the dense interaction networks of real-world problems and the sparse connectivity of physical chips creates a fundamental bottleneck.
The Reality of Physical Topologies
Modern quantum annealing architectures feature fixed, localized connectivity graphs. As highlighted by Jan-Nico Zaech et al. in Adiabatic Quantum Computing for Multi Object Tracking and Han Yao Choong et al. in Quantum Annealing for Single Image Super-Resolution, near-term processors are severely constrained by low qubit counts and restricted physical layouts.
When a real-world problem requires a fully connected graph—where every variable potentially interacts with every other variable, such as in jet clustering (Andrea Delgado and Jesse Thaler in Quantum Annealing for Jet Clustering with Thrust) or multi-agent pathfinding (Thore Gerlach and Loong Kuan Lee in Hybrid Quantum-Classical Multi-Agent Pathfinding)—it cannot be mapped one-to-one onto the hardware.
The Minor Embedding Tax
To circumvent sparse physical connectivity, researchers rely on a technique called minor embedding. If a single logical variable needs to communicate with more neighbors than a single physical qubit can reach, multiple physical qubits are chained together via strong ferromagnetic couplings to act as a single, unified logical variable. This process was demonstrated in early biophysical optimization work by Alejandro Perdomo‐Ortiz et al. in Finding low-energy conformations of lattice protein models by quantum annealing.
While minor embedding makes problem mapping physically possible, it introduces a steep resource tax:
- Super-Linear Resource Growth: As problem complexity scales, the number of physical qubits required grows much faster than the number of logical variables. Tony Tran et al. in A Hybrid Quantum-Classical Approach to Solving Scheduling Problems and Matteo Farina et al. in Quantum Multi-Model Fitting note that this overhead severely limits the practical scale of solvable problems. In dense problems, Marcel Seelbach Benkner et al. in Adiabatic Quantum Graph Matching with Permutation Matrix Constraints show that a quadratic increase in logical variables can translate into a quartic explosion in physical hardware requirements.
- Chain Instability and Noise: To force a chain of physical qubits to behave as a single variable, the internal coupling between them must be highly rigid. However, Tolga Birdal et al. in Quantum Permutation Synchronization explain that as these chains grow longer, they become increasingly susceptible to "breaking" during the annealing process. When a chain breaks, its constituent qubits settle into conflicting states, destroying the validity of the solution and causing success probabilities to plummet (Federica Arrigoni et al. in Quantum Motion Segmentation; Harshil Bhatia et al. in CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes).
The Quadratization Bloat
The physical limitations of quantum annealers extend beyond spatial layout to the mathematical structure of the interactions themselves. Quantum hardware natively supports only quadratic (two-body) interactions. Yet, many foundational computer science problems—such as Boolean Satisfiability (SAT) or neuro-symbolic reasoning—inherently feature higher-order, multi-body constraints.
To execute these higher-order polynomials on quadratic hardware (Pooya Ronagh et al. in Solving constrained quadratic binary problems via quantum adiabatic evolution), researchers must perform quadratization. This technique breaks down a multi-body term (e.g., $x_1 x_2 x_3$) by introducing auxiliary or "slack" variables that represent the product of pairs (Nicholas Chancellor and P. A. Warburton in Circuit design for multi-body interactions in superconducting quantum annealing systems with applications to a scalable architecture).
This creates a compounding bottleneck. The addition of auxiliary qubits inflates the dimensionality of the problem space (Tuhin Sahai et al. in Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms; Anshujit Sharma et al. in Augmenting an electronic Ising machine to effectively solve boolean satisfiability). As the variable count expands, the interaction graph becomes denser, which in turn demands even longer minor-embedding chains (Krzysztof Domino et al. in Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing), pushing the problem beyond physical hardware capacities.
Algorithmic Escape Hatches
To bridge the gap between theoretical optimization models and physical hardware constraints, researchers have developed several algorithmic strategies:
1. Decomposition and Iterative Frameworks
Instead of attempting a "one-shot" global optimization, large problems can be broken down into a sequence of smaller, unconstrained subproblems that natively fit the hardware's topology. Marcel Seelbach Benkner et al. demonstrated this in Q-Match: Iterative Shape Matching via Quantum Annealing, utilizing an iterative cyclic expansion to scale solvable computer vision instances from 4 points to over 500 points. Similarly, Nicola Franco et al. in Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness leveraged Dantzig-Wolfe decomposition to reduce the required qubit count by up to 90% for neural network verification tasks.
2. Constraint Pruning and Approximation
When exactness is too costly, mathematical precision can be traded for physical feasibility. In Approximate Approximation on a Quantum Annealer, the authors showed that intentionally pruning 50% to 80% of a problem's less critical constraints allows for the mapping of 30% larger problem instances onto a chip while maintaining a manageable deviation from the true global optimum.
3. Density-Aware Formulations
Rather than focusing solely on minimizing the number of logical variables, modern QUBO design prioritizes minimizing coupling density. As Jonas Nüßlein and Sebastian Zielinski discovered in Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization, the density of variable connections is often a stronger predictor of quantum annealing performance than the raw qubit count. Formulations that minimize interaction density directly shorten physical chain lengths, mitigating noise and significantly boosting solution quality.
Key Foundational Work
Finding low-energy conformations of lattice protein models by quantum annealing (2012) — contributed 1 concept elements to this direction.