Skip to content

Lesson 35: Quantum Annealing and the Adiabatic Model

35.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the adiabatic theorem and the runtime condition involving the spectral gap.
  2. Describe adiabatic quantum computation (AQC) and its equivalence to the circuit model.
  3. Distinguish AQC from quantum annealing as implemented by D-Wave.
  4. Analyse quantum tunnelling versus classical thermal hopping.
  5. Assess the experimental evidence for and against a quantum-annealing speed-up.

35.2 The Adiabatic Theorem

Statement. If a system starts in the ground state of \(H(0)\) and the Hamiltonian is varied slowly enough, the system remains in the instantaneous ground state of \(H(t)\) throughout.

The quantitative condition. Let \(s = t/T \in[0,1]\) and let

\[ \Delta(s) = E_1(s) - E_0(s) \]

be the spectral gap between the ground and first excited states. The evolution stays adiabatic provided

\[ \boxed{\ T \ \gg\ \frac{\displaystyle\max_{s}\left|\left\langle E_1(s)\left|\frac{dH}{ds}\right|E_0(s)\right\rangle\right|} {\displaystyle\min_{s}\Delta(s)^{2}}\ } \]

Read the exponent carefully. Runtime scales as \(1/\Delta_{\min}^{2}\). Halving the minimum gap quadruples the required time.

The Landau–Zener formula makes this precise for a two-level crossing: the probability of an unwanted transition out of the ground state is

\[ P_{\text{excite}} = \exp\!\left(-\frac{2\pi\Delta_{\min}^{2}}{4\hbar\,|d(E_1-E_0)/dt|}\right) . \]

35.3 Adiabatic Quantum Computation

The construction

\[ H(s) = (1-s)\,H_B \;+\; s\,H_C, \qquad s: 0 \to 1 \]
Component Role
\(H_B = -\sum_i X_i\) initial Hamiltonian; ground state is \(\lvert +\rangle^{\otimes n}\) — easy to prepare
\(H_C\) problem Hamiltonian; its ground state is the answer

Procedure. Prepare \(|+\rangle^{\otimes n}\), ramp \(s\) from 0 to 1 over time \(T\), then measure in the computational basis.

Equivalence to the circuit model

Theorem (Aharonov, van Dam, Kempe, Landau, Lloyd, Regev, 2004). AQC and the circuit model are polynomially equivalent. Anything computable in the circuit model is computable adiabatically with only polynomial overhead, and vice versa.

So AQC is universal — it is not a weaker model. But this equivalence requires arbitrary \(k\)-local Hamiltonians, whereas real annealers implement only the restricted 2-local stoquastic Ising form.

The gap problem

The runtime is governed entirely by \(\Delta_{\min}\), and this is where hardness reappears:

\(\Delta_{\min}\) scaling Runtime Verdict
\(\Omega(1/\mathrm{poly}(n))\) polynomial efficient
\(\Theta(2^{-cn})\) exponential no advantage

For NP-hard problems the gap is generically exponentially small, so AQC gives no free lunch — exactly as expected, since AQC is equivalent to the circuit model and BQP is not known to contain NP.

The gap is also hard to predict. Computing \(\Delta_{\min}\) for a given instance is itself an exponentially hard eigenvalue problem, so you cannot know in advance how slowly to anneal.

35.4 Quantum Annealing in Practice

What D-Wave actually implements

\[ H(s) = -\frac{A(s)}{2}\sum_i \sigma^x_i \;+\; \frac{B(s)}{2}\left(\sum_ih_i\sigma^z_i + \sum_{i<j}J_{ij}\sigma^z_i\sigma^z_j\right) \]

with \(A(0)\gg B(0)\) and \(A(1)\ll B(1)\): the transverse field is ramped down while the problem Hamiltonian is ramped up.

Five ways it differs from ideal AQC

Ideal AQC D-Wave quantum annealing
Closed system, zero temperature Open system at ~15 mK, coupled to a thermal bath
Arbitrary \(k\)-local \(H\) 2-local Ising only, stoquastic (no sign problem)
Full connectivity sparse Pegasus/Zephyr graph — needs minor embedding
Coherent throughout coherence \(\sim\) ns; the anneal lasts \(\mu\)s ⟹ mostly incoherent
Provably universal not universal — stoquastic 2-local is not known to be universal

Stoquasticity matters. A Hamiltonian is stoquastic if all off-diagonal elements are non-positive in the computational basis. Such Hamiltonians have no sign problem, and Quantum Monte Carlo can simulate them efficiently in many regimes — which is a direct obstacle to claiming exponential advantage.

Hardware scale

Generation Qubits Topology Degree
D-Wave 2000Q (2017) 2048 Chimera 6
Advantage (2020) 5640 Pegasus 15
Advantage2 (2024) 4400+ Zephyr 20

Minor embedding maps a dense logical problem onto this sparse graph by representing one logical qubit as a chain of ferromagnetically coupled physical qubits. Embedding a complete graph \(K_n\) into Pegasus needs \(O(n^2)\) physical qubits, so 5640 physical qubits support only about \(\mathbf{180}\) fully connected logical variables. Chain breaks (when a chain's qubits disagree) are a major error source.

35.5 Tunnelling versus Thermal Hopping

This is the physical intuition for why quantum annealing might help.

Classical simulated annealing must climb over an energy barrier. The escape rate follows the Arrhenius law:

\[ P_{\text{thermal}} \sim \exp\!\left(-\frac{E_{\text{barrier}}}{k_BT}\right) \]

— it depends on the barrier height only.

Quantum annealing can tunnel through the barrier. The WKB tunnelling amplitude is

\[ P_{\text{tunnel}} \sim \exp\!\left(-\frac{w\sqrt{E_{\text{barrier}}}}{\Gamma}\right) \]

— it depends on both the height and the width \(w\).

\[ \boxed{\ \textbf{Quantum annealing should win for barriers that are \emph{tall but thin}.}\ } \]

Where it should lose: wide, shallow barriers, and rugged "golf-course" landscapes with no structure at all.

Experimental confirmation. Boixo et al. (2016) constructed a synthetic problem with deliberately tall, thin barriers and measured a \(10^{8}\times\) speed-up of D-Wave over simulated annealing on a single core. But Denchev et al. and subsequent work showed that Quantum Monte Carlo — a classical algorithm that also tunnels — matched the annealer's scaling. The advantage was over simulated annealing specifically, not over the best classical method.

35.6 The Evidence, Weighed

Claims and rebuttals

Claim Rebuttal
\(10^{8}\times\) over simulated annealing (Google, 2016) matched by Quantum Monte Carlo, a classical algorithm
Speed-up on 3-D spin glasses matched by specialised classical solvers (Selby's algorithm)
Practical advantage on real applications no peer-reviewed demonstration on an industrial problem to date
Quantum effects are present in the device ✓ this is well established — entanglement and tunnelling have been directly measured

The consensus position (2024): D-Wave devices are genuinely quantum — entanglement during the anneal has been experimentally verified — but no scaling advantage over the best classical algorithms has been demonstrated on any problem of practical interest. The 2023–24 results on quantum simulation of spin dynamics (as opposed to optimisation) are more promising and are where the strongest current claims lie.

Where annealing is nonetheless useful

  • Sampling rather than optimisation (Boltzmann sampling for QBMs, L33).
  • Quantum simulation of the transverse-field Ising model itself — a physics goal, not an optimisation one.
  • Hybrid solvers (D-Wave's own LeapHybrid) that use the QPU as one heuristic among several inside a classical framework; these are competitive, but the classical parts do most of the work.

QAOA versus quantum annealing

QAOA (gate model) Quantum annealing
Hardware universal gate device special-purpose annealer
Qubits available ~100–1000 ~5000
Connectivity limited, but SWAPs allow any graph sparse, needs embedding
Error correction possible in principle none
Parameters \(2p\), classically optimised annealing schedule only
Theoretical guarantee exact as \(p\to\infty\) exact as \(T\to\infty\)
Universality universal not universal (stoquastic 2-local)

They are the same idea — QAOA is Trotterised annealing (L34 §3.1) — implemented on different hardware. Annealers have more qubits; gate devices have more control and a path to error correction.

35.7 Solved Problems

Problem 1 — Annealing time from the spectral gap

A problem has \(\Delta_{\min} = 0.01\) energy units and \(\max\|dH/ds\| = 10\). Estimate the required annealing time. Repeat for \(\Delta_{\min} = 0.001\).

Solution.

\[ T \gg \frac{\max\|dH/ds\|}{\Delta_{\min}^{2}} \]

Case 1: \(\Delta_{\min} = 0.01\).

\[ T \gg \frac{10}{(0.01)^{2}} = \frac{10}{10^{-4}} = \mathbf{10^{5}}\ \text{time units} \]

Case 2: \(\Delta_{\min} = 0.001\).

\[ T \gg \frac{10}{10^{-6}} = \mathbf{10^{7}}\ \text{time units} \]

A 10× smaller gap requires a 100× longer anneal — the quadratic dependence in action.

Why this is the central difficulty. For NP-hard problems the gap typically closes as \(\Delta_{\min}\sim 2^{-cn}\), so

\[ T \sim 2^{2cn} \]

— exponential, and worse than the classical brute-force \(2^{n}\) unless \(c < \frac12\). Quantum annealing does not evade NP-hardness.

Problem 2 — Tunnelling versus thermal escape, quantified

A barrier has height \(E_b = 10\) (in units of \(k_BT\)) and width \(w\). Compare thermal and tunnelling escape rates for \(w = 1\) and \(w = 10\), with transverse field \(\Gamma = 2\).

Solution.

Thermal rate (independent of width):

\[ P_{\text{thermal}} \sim e^{-E_b/k_BT} = e^{-10} = \mathbf{4.54\times10^{-5}} \]

Tunnelling rate.

\[ P_{\text{tunnel}} \sim \exp\!\left(-\frac{w\sqrt{E_b}}{\Gamma}\right) = \exp\!\left(-\frac{w\sqrt{10}}{2}\right) = \exp(-1.5811\,w) \]

For \(w = 1\) (thin barrier):

\[ P_{\text{tunnel}} = e^{-1.5811} = \mathbf{0.2058} \]
\[ \frac{P_{\text{tunnel}}}{P_{\text{thermal}}} = \frac{0.2058}{4.54\times10^{-5}} = \mathbf{4534\times} \]

Quantum annealing is ~4500× faster. ✓

For \(w = 10\) (wide barrier):

\[ P_{\text{tunnel}} = e^{-15.811} = \mathbf{1.36\times10^{-7}} \]
\[ \frac{P_{\text{tunnel}}}{P_{\text{thermal}}} = \frac{1.36\times10^{-7}}{4.54\times10^{-5}} = \mathbf{0.0030} \]

Quantum annealing is ~330× slower. ✗

Summary table.

Barrier \(P_{\text{thermal}}\) \(P_{\text{tunnel}}\) Winner
Tall, thin (\(w=1\)) \(4.5\times10^{-5}\) \(0.21\) quantum, 4500×
Tall, wide (\(w=10\)) \(4.5\times10^{-5}\) \(1.4\times10^{-7}\) classical, 330×
\[ \boxed{\ \text{Quantum annealing helps only on landscapes with tall, thin barriers.}\ } \]

Whether real-world optimisation landscapes have this character is an empirical question with no general answer — which is precisely why the advantage claims have been so contested.

Problem 3 — Minor embedding cost

A dense QUBO with 100 fully connected variables is to be run on a Pegasus-topology annealer with 5640 qubits and degree 15. Estimate the physical qubits needed. Will it fit?

Solution.

Embedding a complete graph \(K_n\) into Chimera requires \(\approx n^2/4\) physical qubits; Pegasus improves this to roughly

\[ \text{physical qubits} \approx \frac{n^{2}}{7} \ \text{(empirical for Pegasus)} \]

For \(n = 100\):

\[ \frac{100^{2}}{7} = \frac{10{,}000}{7} \approx \mathbf{1430\ \text{physical qubits}} \]

Fits comfortably within 5640 ✓.

Chain length.

\[ \bar\ell = \frac{1430}{100} \approx \mathbf{14\ \text{physical qubits per logical variable}} \]

Consequences of long chains.

  1. Chain breaks. Each chain must remain ferromagnetically aligned. If the chain coupling \(J_{\text{chain}}\) is too weak the chain breaks; if too strong it dominates the problem energy scale and washes out the actual \(h_i, J_{ij}\) values. With \(\ell = 14\), chain-break rates of 10–30 % are typical.
  2. Reduced precision. The device has finite analogue precision (~4–5 bits) on \(h\) and \(J\). Strong chain couplings consume much of that dynamic range, leaving the problem couplings poorly resolved.
  3. Effective problem-size limit.
\[ n_{\max} \approx \sqrt{7\times5640} \approx \mathbf{199\ \text{fully connected variables}} \]

The practical conclusion. A 5640-qubit annealer solves dense problems of only ~180–200 variables — a size that classical solvers handle exactly in seconds (Gurobi routinely solves dense QUBOs of several hundred variables). Sparse problems that map natively fare much better, which is why published annealing successes are almost always on problems whose graph matches the hardware.

Problem 4 — Reading an annealing experiment critically

A paper reports that a D-Wave annealer solved a 500-variable problem in 20 µs while "a classical computer took 30 minutes". List five questions you must ask before accepting a claim of quantum advantage.

Solution.

1. What was the classical baseline? If it was simulated annealing with default parameters, the comparison is weak. The correct baselines are the best available classical algorithms: Gurobi/CPLEX, Selby's algorithm for Chimera-structured problems, parallel tempering, or Quantum Monte Carlo. Many claimed advantages evaporate against these.

2. Was the total time measured, or only the anneal time? 20 µs is the anneal time. Real wall-clock time includes programming the QPU (~10 ms), readout (~100 µs per sample), thermalisation between samples, and the classical minor-embedding computation (which can take minutes and is often excluded). Honest end-to-end timing typically adds three to four orders of magnitude.

3. How many samples were needed, and was the optimum verified? An annealer returns a distribution. If 10 000 anneals were needed to see the optimum once, the true cost is \(10^{4}\times20\ \mu\mathrm{s} = 0.2\) s, not 20 µs. And was the returned solution verified optimal, or just the best seen?

4. Was the problem native to the hardware graph? If the problem was generated to match Chimera/Pegasus connectivity, it is not representative — and such instances are precisely the ones specialised classical solvers (Selby) handle easily. Genuine applications rarely have hardware-matched topology.

5. What is the scaling, not the single data point? A single problem size proves nothing. The question is how time-to-solution grows with \(n\) for quantum versus classical. Advantage means a better exponent or a better polynomial degree, not a better constant on one instance. Nearly every retracted advantage claim failed on this point.

A sixth question worth adding: was the comparison run on comparable hardware budgets? A $15M annealer versus one laptop core is not a fair fight; the honest comparison is against a classical cluster of equivalent cost.

Problem 5 — Designing an annealing application end to end

Design a quantum-annealing solution for portfolio optimisation: select \(k\) assets from \(N\) to maximise expected return subject to a risk constraint. Specify the QUBO, embedding and honest expectations.

Solution.

Classical formulation (Markowitz).

\[ \max_{\vec x\in\{0,1\}^{N}} \ \ \vec\mu^{T}\vec x \;-\; q\,\vec x^{T}\Sigma\vec x \qquad\text{subject to}\qquad \sum_i x_i = k \]

where \(\vec\mu\) is expected returns, \(\Sigma\) the covariance matrix, and \(q\) the risk-aversion parameter.

QUBO formulation. Move the constraint into a penalty:

\[ \min_{\vec x}\ \ -\vec\mu^{T}\vec x + q\,\vec x^{T}\Sigma\vec x + \lambda\Big(\sum_ix_i - k\Big)^{2} \]
\[ Q_{ii} = -\mu_i + q\Sigma_{ii} + \lambda(1 - 2k), \qquad Q_{ij} = 2q\Sigma_{ij} + 2\lambda \ (i<j) \]

(using \(x_i^2 = x_i\) to fold the diagonal of the penalty into the linear term).

Choosing \(\lambda\). It must exceed the maximum objective swing from adding or removing one asset: \(\lambda > \max_i|\mu_i| + 2q\max_i\sum_j|\Sigma_{ij}|\).

Embedding. \(\Sigma\) is dense — every pair of assets is correlated — so this is a complete graph \(K_N\). From Problem 3, \(N \approx 180\) is the ceiling.

Honest expectations.

Aspect Reality
Problem size ≤ 180 assets on current hardware
Classical baseline Gurobi solves 180-asset QUBOs to proven optimality in seconds
Quantum result a heuristic solution, no optimality certificate
Wall-clock seconds including embedding and sampling — comparable, not faster
Solution quality typically within 1–5 % of optimal, sometimes exactly optimal
Verdict no advantage today

Where annealing could add value nonetheless.

  1. Solution diversity. Annealers naturally return many near-optimal portfolios, which is genuinely useful for scenario analysis — an exact solver returns one.
  2. Real-time re-optimisation. Once embedded, re-running with updated \(\vec\mu\) is fast, since the expensive embedding is reusable.
  3. As one heuristic among several inside a hybrid solver, contributing diversity to a portfolio of methods.

The recommendation to give a client. Use classical solvers for production. Use the annealer for research, benchmarking and building institutional readiness — so that if hardware improves by the one to two orders of magnitude needed, the pipeline already exists. Do not claim, or accept a claim of, current advantage.

35.8 Practice Problems

  1. Compute \(T\) for \(\Delta_{\min}=0.05\) and \(\max\|dH/ds\| = 4\). [Ans: \(T\gg1600\)]
  2. Compare tunnelling and thermal rates for \(E_b = 20\), \(w = 2\), \(\Gamma = 3\). [Ans: tunnel \(e^{-2.98}=0.051\) vs thermal \(e^{-20}=2\times10^{-9}\) — quantum wins]
  3. How many logical variables fit fully connected in 2048 Chimera qubits? [Ans: \(\approx\sqrt{4\times2048}\approx 90\)]
  4. Why does a stoquastic Hamiltonian limit the claim of exponential advantage?
  5. State the adiabatic theorem and explain the \(1/\Delta^2\) scaling.
  6. Give three differences between ideal AQC and D-Wave annealing.
  7. Explain why QAOA and quantum annealing are the same algorithm on different hardware.

35.9 Summary

  • Adiabatic theorem: stay in the ground state if \(T \gg \max\|dH/ds\|/\Delta_{\min}^{2}\) — runtime scales as the inverse square of the spectral gap.
  • AQC with \(H(s) = (1-s)H_B + sH_C\) is polynomially equivalent to the circuit model, so it is universal — but for NP-hard problems the gap is generically exponentially small.
  • D-Wave quantum annealing differs from ideal AQC in five ways: open system, 2-local stoquastic only, sparse connectivity needing minor embedding, largely incoherent, and not known to be universal.
  • Tunnelling beats thermal hopping for tall, thin barriers (\(e^{-w\sqrt{E_b}/\Gamma}\) versus \(e^{-E_b/k_BT}\)) and loses for wide ones — whether real landscapes are favourable is an open empirical question.
  • Evidence: quantum effects in the hardware are confirmed; no scaling advantage over the best classical algorithms has been demonstrated on a problem of practical interest. Claimed speed-ups have repeatedly been matched by Quantum Monte Carlo or specialised solvers.
  • Minor embedding limits dense problems to ~180 fully connected variables on a 5640-qubit machine — a size classical solvers handle exactly in seconds.
  • QAOA is Trotterised annealing. Annealers offer more qubits; gate devices offer control, universality and a path to error correction.

Unit III is now complete. You can encode classical data, build quantum kernels and variational classifiers, compute gradients by parameter shift, recognise and mitigate barren plateaus, and formulate and solve combinatorial problems by QAOA and annealing — with a calibrated sense of what is demonstrated and what is aspiration.

Next lesson: L36 — The quantum software landscape (Unit IV begins).

Practise now: unit3-qml-lab.html → Annealing Lab: draw an energy landscape, set the temperature and transverse field, and race a simulated-annealing walker against a tunnelling one.