Quantum Annealing

Optimization problems ask: among all possible solutions, find the one with the lowest cost. Classical simulated annealing searches by hopping between solutions stochastically, using temperature to escape local minima. Quantum annealing replaces thermal hopping with quantum tunneling: the system can pass through energy barriers rather than over them, potentially escaping local minima that would trap a classical optimizer. D-Wave Systems has built quantum annealers with thousands of qubits and sold them commercially since 2011, making quantum annealing the first commercially deployed quantum computing technology.

The details

Ising model and QUBO. The optimization problem must be reformulated as a quadratic unconstrained binary optimization (QUBO) or equivalently as an Ising spin Hamiltonian:

$H_{\text{problem}} = \sum_i h_i \sigma_i^z + \sum_{i<j} J_{ij} \sigma_i^z \sigma_j^z$

where $h_i$ are local fields and $J_{ij}$ are couplings between spins. Finding the ground state of this Hamiltonian gives the optimal solution. Many combinatorial problems map to Ising/QUBO: max-cut, graph coloring, portfolio optimization, traffic routing, drug discovery, and the traveling salesman problem.

How quantum annealing works. The annealer starts in the ground state of a simple transverse-field Hamiltonian $H_{\text{initial}} = -\Gamma \sum_i \sigma_i^x$, whose ground state is a uniform superposition over all spin configurations. It then slowly interpolates:

$H(s) = (1 - s) H_{\text{initial}} + s \, H_{\text{problem}}, \quad s: 0 \to 1$

If this schedule is slow enough (adiabatic theorem), the system remains in the ground state throughout, ending in the ground state of $H_{\text{problem}}$, the optimal solution. In practice, schedules are too fast, and the system may land in an excited (suboptimal) state. Multiple anneal runs are performed and the best result is kept.

Tunneling vs thermal hopping. In simulated annealing, a system must climb over an energy barrier to escape a local minimum; this requires thermal fluctuations and takes time exponential in barrier height. Quantum tunneling allows passage through the barrier with amplitude proportional to $e^{-S}$ where $S$ is the barrier action. For tall, narrow barriers, tunneling is faster; for wide barriers, thermal hopping may be preferable.

D-Wave hardware. D-Wave uses superconducting flux qubits arranged in a sparse graph topology called Pegasus (5,000+ qubits in the Advantage system). Each qubit is a superconducting loop that can be in a flux-up or flux-down state. Couplers between qubits implement the $J_{ij}$ terms. The sparse connectivity is a key limitation: problems with dense couplings must be embedded into the Pegasus graph via minor embedding, which inflates the effective qubit count and introduces approximation errors. A 100-variable fully connected problem might require 2,000 or more physical qubits after embedding.

Comparison to QAOA and simulated annealing. QAOA is a gate-based quantum algorithm for the same class of optimization problems, running on universal quantum computers. QAOA is more flexible but requires deeper circuits and is more sensitive to noise. Simulated annealing is a classical metaheuristic with similar objectives: D-Wave annealers must be compared against highly tuned classical solvers, not naive SA implementations.

Small QUBO example with D-Wave Ocean SDK:

import dimod

# Simple QUBO: minimize x0 + x1 - 2*x0*x1
# Solution: x0=1, x1=1 gives cost 1+1-2=0 (minimum)
Q = {(0, 0): 1, (1, 1): 1, (0, 1): -2}

bqm = dimod.BinaryQuadraticModel.from_qubo(Q)

# Sample classically (swap for DWaveSampler for real hardware)
sampler = dimod.ExactSolver()
response = sampler.sample(bqm)

best = response.first
print(f"Best solution: {best.sample}, energy: {best.energy}")
# Expect: {0: 1, 1: 1}, energy: 0.0

# For D-Wave hardware:
# from dwave.system import DWaveSampler, EmbeddingComposite
# sampler = EmbeddingComposite(DWaveSampler())
# response = sampler.sample(bqm, num_reads=1000)

Current state and hybrid solvers. D-Wave’s Advantage2 system exceeds 5,000 qubits. D-Wave also offers Leap hybrid solvers that partition large problems: a classical solver handles the overall problem structure while the quantum annealer tackles dense subproblems. This hybrid approach currently outperforms pure quantum annealing for most practical problem sizes.

The speedup debate. Despite years of study, no rigorous quantum speedup over the best classical algorithms has been demonstrated on D-Wave hardware. Carefully tuned classical solvers (simulated annealing, tabu search, branch and bound) remain competitive or superior on most tested problem instances. The debate continues: proponents argue that future hardware or specific problem structures will show clear quantum advantage; skeptics note that the sparse connectivity and thermal noise substantially limit the tunneling advantage.

Why it matters for learners

Quantum annealing is historically significant as the first deployed commercial quantum technology and has driven substantial research into QUBO formulations. Understanding it requires grasping the Ising model (the universal language of combinatorial optimization in this context), the adiabatic theorem, and the practical differences between hardware topology and problem structure. It is also a case study in how difficult it is to demonstrate genuine quantum speedup, even with purpose-built hardware.

Common misconceptions

Misconception 1: D-Wave machines are universal quantum computers. D-Wave annealers are specialized hardware designed for optimization. They cannot run arbitrary quantum circuits, implement Grover’s algorithm, or perform quantum error correction. They are fundamentally different from gate-based quantum computers from IBM, Google, or Quantinuum.

Misconception 2: Quantum annealing has been proven faster than classical methods. No problem instance has been identified where D-Wave hardware demonstrably outperforms the best classical solvers with statistical certainty. Performance comparisons are highly sensitive to which classical algorithm is chosen, how parameters are tuned, and the structure of the problem instance.

Misconception 3: More qubits means better solutions. D-Wave’s qubit count has grown from 128 to 5,000+, but the useful effective size of problems solved has not grown proportionally. Sparse connectivity requires costly embedding, and thermal noise at the operating temperature (15 millikelvin) limits coherence. Raw qubit count is a poor proxy for problem-solving capability on annealers.

See also

• Adiabatic Quantum Computing
• QAOA
• Quantum Advantage
• Noisy Intermediate-Scale Quantum (NISQ)
• Quantum Speedup