Quantum Annealing — padho.wiki

In short

Quantum annealing is a specialised form of adiabatic quantum computing aimed at one target: solving combinatorial optimisation problems in Ising or QUBO form. You encode your problem as an Ising energy function E(z) = \sum_i h_i z_i + \sum_{ij} J_{ij} z_i z_j with spin variables z_i \in \{-1, +1\}. You start the quantum system in the ground state of a transverse-field Hamiltonian H_0 = -\sum_i X_i (a uniform superposition). You slowly ramp the transverse field down while ramping the Ising couplings up, arriving at H_p = \sum_i h_i Z_i + \sum_{ij} J_{ij} Z_i Z_j. You measure. The bit-string you get is (hopefully) the optimum. The crucial physical claim: where classical simulated annealing crosses tall energy barriers by thermal fluctuation (requiring temperature \gg barrier height), quantum annealing tunnels through them via quantum superposition. For certain landscape geometries — tall thin barriers — tunnelling is asymptotically faster than thermal escape. D-Wave, a Canadian company, has built quantum annealers since 2011 on superconducting flux qubits: Chimera topology (2011–2017), Pegasus (2020+), Zephyr (2023+), now at 5000+ qubits with 20 couplers per qubit. They ship real hardware to real customers (Volkswagen, NASA, Lockheed, several banks) running real QUBO jobs. Hype check: after fifteen years of benchmarks, no convincing quantum advantage over well-tuned classical solvers has been demonstrated for any practical problem. D-Wave's hardware is good at being a quantum annealer; classical simulated annealing and parallel tempering are also good at being classical annealers. On most real problems they finish in comparable time. This chapter builds the Ising encoding, explains the physics of tunnelling, walks through minor-embedding onto Pegasus, and covers the honest status of quantum speedup.

Suppose a logistics company asks you: given 30 delivery locations in Mumbai and a single auto-rickshaw, what is the shortest route that visits every location? Or: given a set of shifts to fill at a hospital and a set of nurses with availability constraints, what assignment satisfies the most rules? Or: given a portfolio of 50 stocks, what weighting minimises risk at a target return?

These are combinatorial optimisation problems. They are everywhere in industry. Almost none of them can be solved exactly in polynomial time — they are NP-hard. Instead, you reach for heuristics: simulated annealing, parallel tempering, tabu search, genetic algorithms, linear-programming relaxations. These are the workhorses of operations research.

Quantum annealing is a proposed quantum heuristic for the same class of problems. The idea dates to 1998–2000 in papers by Finnila, Kadowaki and Nishimori, and Farhi, Goldstone, Gutmann and Sipser [1]. The pitch is sharp: classical simulated annealing explores energy landscapes by accepting uphill moves with Boltzmann probability — a thermal random walk. Quantum annealing explores by preparing a quantum state that is a superposition over all configurations, then tunnelling through energy barriers that thermal escape would need exponentially-rare fluctuations to cross. For the right kind of landscape, tunnelling is faster.

In 2011, a Canadian company called D-Wave Systems shipped the first commercial quantum annealer. Since then they have scaled from 128 qubits to over 5000. Their machines solve Ising-form problems (equivalently, QUBO — Quadratic Unconstrained Binary Optimisation) on real hardware that real customers pay for. You can submit a job today via the cloud and it will return a bit-string in microseconds. The question, which this chapter will answer carefully, is whether that bit-string is any better — or any faster to compute — than what a good classical algorithm would give you on the same problem.

This chapter builds the full story: the Ising encoding of combinatorial problems, the physics of tunnelling vs thermal escape, the detailed architecture of D-Wave's hardware (flux qubits, Pegasus topology, annealing schedule), the minor-embedding step that maps your problem graph onto the hardware graph, and the hybrid classical-quantum workflows that D-Wave now pushes. It ends with a hype-check on speedup claims.

Ising energy functions — the target class

Quantum annealing solves one specific kind of problem: minimisation of an Ising energy function.

Ising energy function

For n spin variables z_i \in \{-1, +1\}, real local fields h_i, and real couplings J_{ij} (one for each pair (i, j) in some connectivity graph), the Ising energy is

E(z) = \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j.

The problem is: find the spin configuration z^* \in \{-1, +1\}^n that minimises E(z).

Equivalently, using 0/1 variables x_i = (1 - z_i)/2 \in \{0, 1\}, the same problem becomes QUBO:

C(x) = \sum_i a_i x_i + \sum_{i<j} b_{ij} x_i x_j + \text{const.}

Ising and QUBO are interchangeable after a linear substitution; every quantum annealer firmware accepts both.

Why this form is so useful: a huge swath of combinatorial problems reduce to Ising/QUBO. Lucas (2014) catalogued Ising encodings for roughly two dozen NP-hard problems — MaxCut, graph colouring, set cover, vertex cover, travelling salesman, 3-SAT, portfolio optimisation, knapsack, scheduling. Each reduces to a specific pattern of h_i and J_{ij} values. The machine does not need to know which problem you are solving — only the coefficients.

Quick example: MaxCut

Given a graph G = (V, E), assign each vertex i a spin z_i \in \{-1, +1\} (labelling the side of the partition). An edge (i, j) is cut when z_i \neq z_j, equivalently when z_i z_j = -1. The number of cut edges is

\text{cuts}(z) = \sum_{(i,j) \in E} \tfrac{1}{2}(1 - z_i z_j).

Maximising cuts is equivalent to minimising \sum_{(i,j) \in E} z_i z_j. Set h_i = 0 and J_{ij} = 1 for edges, 0 otherwise, and feed this Ising problem to the annealer. The returned spin configuration is the maximum cut.

Quick example: 3-SAT as QUBO

Given a 3-SAT formula, each clause (a \lor b \lor c) can be written as a polynomial penalty that is 0 on satisfying assignments and 1 on violating ones. Summing over clauses gives a QUBO whose minimum is 0 iff the formula is satisfiable. Lucas's paper gives the explicit encoding. Minimising the QUBO solves SAT. This makes quantum annealing a general NP-complete-problem solver — in principle. The catch, as always, is whether "in principle" becomes "in practice" before the universe ends.

The physics — tunnelling vs thermal escape

Here is the core physical argument for quantum annealing, the one that motivates the whole field.

Classical simulated annealing, due to Kirkpatrick, Gelatt, and Vecchi (1983), explores the energy landscape by a Metropolis-Hastings random walk. At temperature T, you accept downhill moves always and uphill moves with probability e^{-\Delta E / kT}. You start at high T (large thermal fluctuations, wide exploration), then slowly cool (accepting fewer uphill moves). Done right, the final state is near the global minimum.

The fundamental obstacle: to cross an energy barrier of height \Delta E, simulated annealing needs temperature comparable to \Delta E. But at temperature \sim \Delta E, the system is already wandering over many states; cooling below this temperature gets you stuck on one side of the barrier. For landscapes with many tall barriers, the cooling schedule must be exponentially slow to escape.

Quantum annealing proposes a different escape route: tunnelling. A quantum particle can cross a potential barrier whose height exceeds its energy, simply by having some amplitude on the other side. The tunnelling rate depends on the width and height of the barrier, not just its height. For tall thin barriers — narrow in configuration space — quantum tunnelling can be exponentially faster than thermal escape. For short wide barriers, thermal wins.

Classical simulated annealing climbs over energy barriers using thermal fluctuations, which requires the temperature to exceed the barrier height. Quantum annealing tunnels through barriers using the spatial spread of the wavefunction — which depends on the barrier's width as well as its height. For narrow barriers, quantum tunnelling is exponentially faster.

The mathematical setup mirrors adiabatic quantum computing exactly. You interpolate

H(s) = A(s)\left(-\sum_i X_i\right) + B(s)\left(\sum_i h_i Z_i + \sum_{ij} J_{ij} Z_i Z_j\right),

where A(s) starts large and ramps to zero, B(s) starts at zero and ramps up. Early in the sweep (small s), the -\sum_i X_i term dominates: its ground state is the uniform superposition |+\rangle^{\otimes n}, "exploring all configurations equally." Late in the sweep (large s), the Ising term dominates: its ground state is a computational-basis state encoding the optimum.

Why the transverse field enables tunnelling: the operator -\sum_i X_i flips spins. A state localised near one local minimum is not an eigenstate of X_i, so the transverse field induces amplitude to flip spins one at a time. If flipping a small number of spins takes you over a barrier to another minimum, you gain amplitude on the other minimum — the essence of tunnelling. The stronger A(s) is early in the sweep, the more quantum delocalisation you have. As A(s) ramps down, the state "settles" into a minimum of the Ising Hamiltonian.

In the adiabatic limit, if you ramp A down and B up infinitely slowly, you end in the exact ground state of H_p (the Ising ground state), as the adiabatic theorem guarantees — provided the spectral gap doesn't vanish. In practice, the ramp takes 10–20 microseconds on current D-Wave hardware, which is fast enough that the evolution is not strictly adiabatic — there is some probability of non-adiabatic transitions to excited states. The machine returns a bit-string that is probably the ground state, or close to it; run the annealer many times and take the best result.

D-Wave hardware — the real machine

D-Wave is not a thought experiment. It is a refrigerator the size of a garden shed, sitting in Burnaby, British Columbia, accepting cloud jobs 24/7. Here is what is inside.

Superconducting flux qubits

Each D-Wave qubit is a flux qubit: a superconducting loop of niobium with a Josephson junction interrupting it. A persistent current circulates around the loop; depending on whether it circulates clockwise or counter-clockwise, the loop's magnetic flux is slightly positive or slightly negative — these two states are the logical |0\rangle and |1\rangle of the qubit. An external magnetic bias tilts the double-well potential, implementing the h_i field in the Ising Hamiltonian.

Qubit-qubit coupling is implemented by inductive coupling between neighbouring loops: when one qubit's current direction flips, it induces a flux change in coupled loops, which pushes their preferred spin direction. The coupling strength J_{ij} is set by a tunable coupler between the loops, controlled by another on-chip flux bias.

The transverse field -X_i is implemented by a non-zero tunnelling amplitude across the Josephson junction — a quantum process that couples the clockwise and counter-clockwise current states. The magnitude of this tunnelling is controlled by a bias on the junction. Ramping the junction bias down during the anneal reduces the tunnelling, suppressing the transverse field — exactly what A(s) \to 0 requires.

Total: a chip with 5000+ flux-qubit loops, 40,000+ couplers, all biased by a grid of DACs (digital-to-analog converters) setting the external flux at each location. The whole chip sits in a dilution refrigerator at ~15 millikelvin — colder than interstellar space — to suppress thermal noise that would otherwise wash out the quantum superposition.

Pegasus and Zephyr topologies

D-Wave's early machines (2011–2017) used the Chimera graph: qubits arranged in 4x4 bipartite "unit cells," with 4 couplers per qubit internally and bridges to neighbouring cells. Chimera's connectivity is sparse — each qubit couples to at most 6 others.

The Pegasus graph (Advantage, 2020+) increases connectivity: each qubit couples to 15 others, in a denser lattice. The Zephyr graph (Advantage2, 2023+) goes further: 20 couplers per qubit on a 7000-qubit target chip. Denser connectivity means fewer ancillary qubits are needed to simulate distant couplings in your problem graph.

Two D-Wave topologies. Chimera (left) has sparse bipartite unit cells with six couplers per qubit — adequate for small embeddings but wasteful of qubits for dense problem graphs. Pegasus (right) has 15 couplers per qubit and supports much denser native embeddings. Zephyr (2023+) pushes further to 20 couplers per qubit.

The annealing schedule

D-Wave exposes two "schedule" functions A(s) and B(s) controlling the transverse and Ising strengths. The default is a pre-calibrated schedule tuned for generic problems: A starts at ~4 GHz and ramps smoothly to zero; B starts at zero and ramps to ~4 GHz. The total anneal time is user-configurable, typically 1–2000 microseconds. Users can also specify custom schedules (pauses, reverse anneals, h-gain ramps) for advanced use.

Minor-embedding — fitting your problem onto the chip

Here is a practical complication. Your problem graph — the set of Ising pairwise interactions (i, j) you specified — probably does not match the hardware graph. If you have a dense all-to-all Ising model (all pairs interact, \binom{n}{2} couplings), and the hardware is a sparse Pegasus lattice (15 couplers per qubit), you cannot map your logical qubits one-to-one onto hardware qubits.

The solution is minor-embedding: represent each logical qubit as a chain of physical qubits, strongly coupled to each other so they all agree on their spin direction. A chain of length \ell uses \ell hardware qubits to behave as one logical qubit. Longer chains can reach more neighbours.

A fully-connected n-qubit Ising problem on Pegasus needs chains of length \approx n/20, using roughly n^2/20 physical qubits total. This is one reason D-Wave needs 5000+ qubits to solve problems of practical size — most of them are used up as chain-bits, not as independent logical qubits. An Advantage machine with 5000 physical qubits can solve a fully-connected logical problem of about 180 qubits. Less dense problem graphs (sparse QUBOs) use embeddings more efficiently.

Finding a good minor-embedding is itself an NP-hard problem (graph minor detection), but heuristics like D-Wave's minorminer work well for typical graphs. The embedding adds additional coupling strength (the "chain strength") to enforce chain consistency, which also costs dynamic range in the hardware's h/J precision.

Hybrid classical-quantum workflows

Modern D-Wave deployments rarely run pure quantum annealing. Instead, they use hybrid solvers that decompose a large problem into smaller subproblems, some solved on the quantum annealer and some on classical hardware. D-Wave's Leap cloud platform offers several hybrid modes:

Quantum annealing + classical post-processing: run QA many times, collect bit-strings, use classical local search to polish the best ones.
QBSolv / dwave-hybrid: partition a large QUBO into overlapping sub-QUBOs, solve each on the QPU, reassemble.
Constrained quadratic models (CQM): accept problems with equality and inequality constraints, handle them via classical LP relaxation + quantum annealing on the core.

Hybrid workflows reflect the practical reality: for real industrial problems, the pure quantum annealing step is one ingredient in a classical pipeline, not a standalone solver.

Worked examples

Example 1: MaxCut on a 5-vertex graph with D-Wave embedding

Solve MaxCut on the following 5-vertex graph: vertices \{1, 2, 3, 4, 5\}, edges \{(1,2), (1,3), (2,3), (2,4), (3,5), (4,5)\}. The graph has 6 edges, and we want to assign each vertex to one of two sides (+1 or -1) maximising the number of cross-edges.

Step 1. Set up the Ising problem. Logical qubit for each vertex, z_i \in \{-1, +1\}. No local fields (h_i = 0 for all i). Coupling J_{ij} = +1 for every edge, 0 otherwise. The Ising energy is

E(z) = z_1 z_2 + z_1 z_3 + z_2 z_3 + z_2 z_4 + z_3 z_5 + z_4 z_5.

Minimising E maximises cuts.

Step 2. Solve by brute force (to know the answer). There are 2^5 = 32 bit-strings. By symmetry, z and -z give the same energy, so 16 distinct configurations. Evaluating shows the minimum energy is -2, achieved by several configurations including z = (+1, -1, -1, +1, +1). That configuration cuts edges (1,2), (1,3), (2,4), (3,5) — four of six edges. Two edges, (2,3) and (4,5), are not cut. Four cuts out of six; MaxCut = 4. Why not all six edges: the triangle (1,2,3) is odd-cycle-frustrated — you cannot two-colour three mutually-adjacent vertices. At least one edge of every odd cycle must remain uncut. This graph contains the triangle \{1,2,3\} and the triangle \{2,3,4,5\} no wait, that's a 4-cycle — let me re-check. The edges are (1,2), (1,3), (2,3), (2,4), (3,5), (4,5). Vertices \{1,2,3\} form a triangle. Vertices \{2,3,4,5\} form a 4-cycle via 2-4-5-3-2. The 4-cycle can be 2-coloured; the triangle cannot. So at least one triangle edge stays uncut. Hence MaxCut \le 5. Direct check confirms = 4.

Step 3. Minor-embed onto Pegasus. The problem graph is small enough that it minor-embeds directly — most Pegasus unit cells have ~15 couplers per qubit, enough to fit a 5-vertex graph with 6 edges into 5 physical qubits directly. No chains needed for this tiny case.

Step 4. Submit to D-Wave. A D-Wave API call looks roughly like:

from dwave.system import DWaveSampler, EmbeddingComposite
sampler = EmbeddingComposite(DWaveSampler())
J = {(1,2): 1, (1,3): 1, (2,3): 1, (2,4): 1, (3,5): 1, (4,5): 1}
h = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
response = sampler.sample_ising(h, J, num_reads=1000)
best_sample = response.first.sample

The machine performs 1000 independent 20-microsecond anneals, returning the 1000 bit-strings. The first.sample is the lowest-energy one found.

Step 5. Expected output. For a well-behaved small problem like this, D-Wave typically returns a ground state in the top \sim 50% of its samples. You might see output like {1: 1, 2: -1, 3: -1, 4: 1, 5: 1} or equivalently \{1: -1, 2: 1, 3: 1, 4: -1, 5: -1\} — the two symmetry-broken ground states — with energy -2 each.

Result. D-Wave delivers one of the MaxCut-optimal configurations for this 6-edge graph in a couple of milliseconds of wall-clock time, including cloud round-trip. Classical brute-force enumeration of 16 configurations takes microseconds on a laptop. For this problem size, D-Wave is slower than classical — as expected: tiny problems are dominated by quantum-to-classical interface overhead.

What this shows. The mechanics are straightforward: encode as Ising, submit, read out. The interesting question is not "can D-Wave solve a 5-vertex MaxCut" — it can, trivially — but "at what problem size does D-Wave start to match or beat classical solvers?" The honest answer, as the hype-check below will show, is: empirically, for practical problems, essentially never yet.

Example 2: Reducing 3-SAT to QUBO

Take a 3-SAT instance with clauses

(x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (x_1 \lor \neg x_2 \lor x_3).

The goal: find (x_1, x_2, x_3) \in \{0,1\}^3 satisfying all three clauses.

Step 1. Clause penalties. Each clause (a \lor b \lor c) is violated exactly when a = b = c = 0. Assign that configuration energy 1, all satisfying configurations energy 0. A polynomial that does this is

P(a, b, c) = (1 - a)(1 - b)(1 - c).

Why this polynomial: it evaluates to 1 only when a = b = c = 0 (each of the three factors equals 1), and to 0 in all other cases (at least one factor is 0). Exactly the penalty we want.

For a negated literal \neg x in the clause, substitute (1 - x) in place of the variable: if the clause is (x_1 \lor x_2 \lor \neg x_3), its penalty is (1 - x_1)(1 - x_2)(1 - (1 - x_3)) = (1 - x_1)(1 - x_2) x_3. The clause is violated when x_1 = 0, x_2 = 0, x_3 = 1.

The three clause penalties:

Clause 1 (x_1 \lor x_2 \lor \neg x_3): P_1 = (1 - x_1)(1 - x_2) x_3.
Clause 2 (\neg x_1 \lor x_2 \lor x_3): P_2 = x_1 (1 - x_2)(1 - x_3).
Clause 3 (x_1 \lor \neg x_2 \lor x_3): P_3 = (1 - x_1) x_2 (1 - x_3).

Total cost: C(x) = P_1 + P_2 + P_3. The formula is satisfiable iff \min_x C(x) = 0.

Step 2. Handle the cubic terms. Each P_k contains a cubic monomial like (1 - x_1)(1 - x_2) x_3 = x_3 - x_1 x_3 - x_2 x_3 + x_1 x_2 x_3. The x_1 x_2 x_3 cubic term is not natively expressible in a 2-local Ising — D-Wave only supports quadratic terms.

The trick: introduce an auxiliary variable. Replace x_1 x_2 with a new variable y, enforcing y = x_1 x_2 via a quadratic penalty:

P_{y}(x_1, x_2, y) = M\left(x_1 x_2 - 2 x_1 y - 2 x_2 y + 3 y\right)

for some large penalty coefficient M > 0. Why this penalty: direct check. (x_1, x_2) = (0,0): P_y = M(0 - 0 - 0 + 3y) = 3My, minimised at y = 0, i.e., y = x_1 x_2 = 0. (x_1, x_2) = (0,1): P_y = M(0 - 0 - 2y + 3y) = My, minimised at y = 0 = x_1 x_2. (x_1, x_2) = (1,0): symmetric. (x_1, x_2) = (1,1): P_y = M(1 - 2y - 2y + 3y) = M(1 - y), minimised at y = 1 = x_1 x_2. So the minimum-energy y is always x_1 x_2, which is what we wanted.

With this substitution, x_1 x_2 x_3 = y x_3 — a quadratic term in the new variables \{x_1, x_2, x_3, y\}. The whole cost function is now a QUBO in 4 variables (originally 3 plus one auxiliary).

Step 3. Assemble. For each clause, introduce one auxiliary variable; total 6 variables for this 3-clause formula. Combine all clause penalties plus all auxiliary-consistency penalties into a single QUBO:

C_{\text{QUBO}}(x, y) = \sum_k P_k^{\text{quad}} + \sum_k M \cdot \text{(auxiliary penalty)}_k.

This QUBO has variables in \{0,1\}^6, with \binom{6}{2} = 15 possible quadratic terms. Most will be zero; the nonzero ones specify the Ising couplings.

Step 4. Convert to Ising and submit. Use x_i = (1 - z_i)/2; this converts the QUBO coefficients into Ising h_i and J_{ij} fields. The final Ising problem is 6 logical qubits. Minor-embed onto Pegasus (trivially, for 6 qubits); submit; read back the bit-string.

Step 5. Interpret. The bit-string of the 3 original variables (x_1, x_2, x_3) is a SAT assignment. For this formula, one satisfying assignment is (1, 1, 0): clause 1 satisfied by x_1 = 1, clause 2 satisfied by x_2 = 1, clause 3 satisfied by x_1 = 1. D-Wave should return this (or (0, 1, 0), (1, 1, 1), etc. — any of the 4 satisfying assignments of this formula).

Result. Any k-SAT formula reduces to a QUBO by the Lucas recipe: cubic terms become quadratic via auxiliary variables, all clauses summed into a cost function. D-Wave hardware can in principle solve SAT — in principle.

What this shows. The embedding pipeline (SAT → QUBO → Ising → minor-embedding → hardware) is mechanical. Where the cleverness hides is in the constants: large M penalties dominate the dynamic range of the hardware's couplers, forcing you to reduce the precision of the interesting couplings. For hard SAT instances, this dynamic-range compression can make the quantum annealer return excited states (unsatisfying assignments) with nontrivial probability — and you fall back to many-sample post-processing. The end-to-end speed depends on how many shots you need and how the hardware precision compares to the problem's scale. This is exactly where D-Wave's practical advantage or disadvantage lives.

Indian context — where quantum annealing shows up in Indian research

Quantum annealing has footholds in Indian industry and academia, though (as of 2026) no D-Wave machine is physically in India — access is via cloud.

TCS Research has published work on quantum optimisation for logistics and finance problems, including QUBO formulations for portfolio optimisation and vehicle routing benchmarked against classical solvers. TCS is a member of the IBM Quantum Network and has explored both gate-model and annealing-based approaches.
QpiAI (Bangalore-based startup, founded 2019) develops quantum-inspired classical annealers and has partnerships for quantum-classical hybrid workflows. Their pitch targets Indian manufacturing and financial services.
IIT Kharagpur's Department of Computer Science and Engineering has a small quantum-optimisation group working on embedding algorithms and QUBO formulations of NP-hard problems.
National Quantum Mission (2023, ₹6000 crore) includes "quantum computing" as one of four pillars; the Mission's roadmap explicitly mentions both gate-model and annealing approaches, with research funding for embedding, encoding, and benchmarking.
Industry pilots: a few Indian financial firms and logistics companies have run pilot QUBO workloads on D-Wave via the cloud, exploring portfolio optimisation, risk modelling, and route planning. Public data on outcomes is sparse, consistent with the global picture: hybrid workflows work, pure-quantum advantage is not demonstrated.

None of these are yet a success story in the sense of "D-Wave beat the classical solver on our production job." They are exploratory, aimed at keeping India's industry quantum-ready for the day speedup materialises.

Hype check

Hype check. Over fifteen years, D-Wave has shipped commercial quantum annealers used by hundreds of customers. In that time, no convincing quantum speedup over well-tuned classical simulated annealing has been demonstrated for any practical optimisation problem. The canonical benchmark studies (Rønnow, Wang, Job, Boixo, Isakov, Wecker, Lidar, Troyer, Martinis — Science, 2014 [2]) ran D-Wave Two on carefully-constructed Ising instances and showed the same scaling as classical simulated annealing, with constant-factor performance comparable or worse. Follow-up work (King et al. 2018, Albash & Lidar 2018, Boixo et al. 2016) has found narrow regimes — small instance classes, highly-structured problems — where D-Wave's hardware exhibits polynomial advantages, but no exponential separation and no clear win on industrial benchmarks. For general NP-hard problems, the minimum spectral gap during the anneal tends to close exponentially, and the machine takes exponential time to find the ground state with high probability — matching classical simulated annealing's exponential scaling. D-Wave's corporate messaging has shifted over time from "quantum speedup" to "hybrid workflows" to "quantum acceleration" — reflecting a community consensus that pure quantum annealing is competitive but not transformative for practical optimisation. This is not a dismissal of the technology: D-Wave has built remarkable hardware that reliably implements a specific, restricted form of adiabatic quantum computing on thousands of qubits. It is a calibration of expectations. If you came here wondering whether quantum annealing will solve your shipping logistics problem 1000x faster than an Intel server, the honest answer as of 2026 is: probably not, and probably not soon. If you came here wondering whether quantum annealing is a legitimate research programme with interesting open questions about tunnelling rates, non-stoquastic Hamiltonians, and hybrid algorithms, the answer is yes, and the next twenty years should be interesting.

Common confusions

"Quantum annealing solves NP-complete problems in polynomial time." No. Quantum annealing encodes NP-complete problems efficiently (as Ising ground-state search), but the spectral gap for NP-hard instances typically closes exponentially, so the runtime is exponential. If quantum annealing polynomially solved NP-complete problems, we would have \text{NP} \subseteq \text{BQP} — not believed.
"D-Wave is just a fancy simulated annealer." No. D-Wave hardware genuinely exhibits quantum coherence at low temperature and implements quantum tunnelling — experimentally verified in several studies. The distinction between "has quantum physics" (yes) and "gives quantum advantage over classical" (no, for practical problems) is the nuanced point.
"Simulated annealing and quantum annealing do the same thing." They explore the same energy landscapes, but by different mechanisms. Simulated annealing uses thermal fluctuations — random bit flips accepted/rejected by Metropolis criterion. Quantum annealing uses the transverse-field superposition — coherent tunnelling. On landscapes with tall thin barriers, tunnelling can be exponentially faster. On landscapes with short wide barriers, thermal is faster. Real problems are a mix.
"D-Wave has 5000 qubits, so it can solve 5000-variable QUBOs." Only sparse ones. Dense (fully-connected) QUBOs require minor-embedding into chains, reducing the effective qubit count by a factor of \sim n/20. On Pegasus, 5000 physical qubits support fully-connected logical problems of about 180 variables.
"You can run Shor's algorithm on D-Wave." No. D-Wave's hardware implements a restricted form of adiabatic quantum computing where H_p is limited to 2-local stoquastic Ising terms. Universal AQC (in the Aharonov–van Dam sense covered in chapter 179) requires non-stoquastic multi-qubit Hamiltonians. D-Wave cannot natively run Shor's factoring or Grover's search; only Ising ground-state search.
"Quantum annealing doesn't need error correction." Also misleading. Current D-Wave hardware is "noisy" — the annealing process has thermal and control-noise errors that reduce success probability. You mitigate this with many samples, chain-break corrections, and hybrid post-processing. For very large problems, error correction-like schemes are actively being researched; they are not yet production-ready.
"Tunnelling always helps." Only for specific landscape shapes. The canonical "tall thin barrier" example (an isolated local minimum separated from the global minimum by a barrier of small spatial extent) is where tunnelling dramatically outperforms thermal escape. Real-world optimisation landscapes are messier, with wide rough barriers, and whether tunnelling helps on a given instance class is an empirical question answered one benchmark at a time.

Going deeper

If you understand that quantum annealing is a specialised form of adiabatic quantum computing aimed at Ising/QUBO minimisation, that the physical mechanism is quantum tunnelling through energy barriers rather than thermal escape over them, that D-Wave implements this on 5000+ superconducting flux qubits with the Pegasus connectivity graph, that minor-embedding maps dense problem graphs onto sparse hardware, and that no clean quantum advantage for practical problems has been demonstrated as of 2026 — you have chapter 180. What follows is the stoquastic restriction, the WKB tunnelling analysis, reverse annealing, and the hybrid-algorithm landscape.

Stoquastic Hamiltonians — a computational ceiling

D-Wave's Ising Hamiltonian H_p = \sum_i h_i Z_i + \sum_{ij} J_{ij} Z_i Z_j combined with transverse field -\sum_i X_i gives a stoquastic Hamiltonian in the computational basis: all off-diagonal matrix elements are real and non-positive. Stoquastic Hamiltonians have a deep connection with classical Monte Carlo simulation — their ground states can be written with non-negative amplitudes, and thermal states admit efficient quantum Monte Carlo algorithms (Path Integral Monte Carlo). In particular, there is evidence (Bravyi, Divincenzo, Oliveira, Terhal 2006) that the complexity class accessible to stoquastic adiabatic evolution is StoqMA, a class believed to be strictly smaller than BQP. So D-Wave hardware — even in the best case — is not universal in the full quantum sense; it is restricted to a subclass of problems possibly solvable classically with quantum-Monte-Carlo-like techniques. Truly universal quantum annealing would require non-stoquastic terms like X_i X_j or X_i Y_j couplings, which D-Wave is actively prototyping but does not yet ship at scale.

WKB approximation for tunnelling rates

The tunnelling rate through a 1D potential barrier of height V_0 and width L is governed by the WKB approximation:

\text{rate} \sim \exp\left(-\frac{2}{\hbar} \int_a^b \sqrt{2m(V(x) - E)}\, dx\right),

where the integral is taken across the classically-forbidden region. For a rectangular barrier, this reduces to \exp(-\kappa L) with \kappa \sim \sqrt{2m V_0}/\hbar. Compare to thermal escape: Arrhenius law gives \exp(-V_0/kT). Setting the two rates equal:

kT_{\text{crossover}} \sim \frac{V_0}{\kappa L}.

Below this temperature, tunnelling dominates; above it, thermal dominates. For narrow barriers (small L), the crossover temperature is high — meaning tunnelling beats thermal at practical temperatures. For wide barriers, tunnelling is negligible and thermal wins. This is the physical root of quantum annealing's conditional advantage.

Reverse annealing

A newer D-Wave feature: instead of the standard forward anneal (A large, B small, ramping down), reverse annealing starts from a classical bit-string (a candidate solution, perhaps from a classical solver), raises A partway (reintroducing transverse field), and re-lowers it. This explores the energy landscape around the starting bit-string — a quantum local search, effectively. Reverse annealing has been shown to outperform forward annealing on some problem classes where a good initial guess is available, linking quantum annealing with classical meta-heuristics like tabu search. It is a promising direction for hybrid workflows.

Non-stoquastic annealers

Research annealers with genuine non-stoquastic terms are under development. The motivation is twofold: (1) access the full BQP complexity class, enabling universal quantum computing in an adiabatic mode; (2) potentially escape the stoquastic-classical-simulability ceiling that might currently cap D-Wave's theoretical speedup. As of 2024–2026, small prototype non-stoquastic annealers have been built (tens of qubits), but no large-scale commercial hardware. If large non-stoquastic annealers are built, they would become legitimate candidates for universal AQC.

Parallel tempering and population annealing

The main classical competitors to quantum annealing are parallel tempering (multiple copies of the system at different temperatures, with periodic swaps) and population annealing (an ensemble of walkers, periodically resampled proportional to Boltzmann weight). These methods, heavily optimised over decades, represent the classical benchmarks that quantum annealers must beat. They routinely handle problem sizes beyond what D-Wave solves natively, at comparable or faster wall-clock times. The hardest open question in quantum annealing research: is there any problem class where QA provably beats parallel tempering, asymptotically? Despite fifteen years of searching, no such class has been convincingly identified.

Where this leads next

Annealing Where It Helps — a careful survey of the problem classes where quantum annealing shows measurable advantage (and where it doesn't).
Adiabatic Quantum Computing — the parent model, of which quantum annealing is a hardware-restricted variant.
QAOA Algorithm — the gate-based discretised adiabatic algorithm, runnable on circuit-model hardware.
D-Wave — the commercial company and its product line.
Local Hamiltonians — the structural class of Hamiltonians used, especially the Ising model.

References

Tadashi Kadowaki, Hidetoshi Nishimori, Quantum annealing in the transverse Ising model (1998), Phys. Rev. E 58 — arXiv:cond-mat/9804280.
Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, Matthias Troyer, Defining and detecting quantum speedup (2014), Science — arXiv:1401.2910.
Andrew Lucas, Ising formulations of many NP problems (2014), Frontiers in Physics — arXiv:1302.5843.
Catherine C. McGeoch, Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice (2014), Morgan & Claypool — publisher landing page.
D-Wave Systems, Technical Description of the D-Wave Quantum Processing Unit — D-Wave docs.
Wikipedia, Quantum annealing.