125
Part Three · B · Algorithms

Quantum optimization and annealing

Cool a metal slowly and its atoms settle into a near-perfect crystal; quench it and they freeze into a disordered glass. Annealing turns a slow change into a good answer. Quantum annealing applies the same idea to optimization: start in the easy ground state of a simple Hamiltonian, change it slowly into one whose ground state encodes the answer, and nature carries the system along. The question that decides everything is how slow is slow enough.

On the plate: two energy levels approaching each other, and whether a sweep stays on the lower one.

The adiabatic theorem

Interpolate H(s)=(1−s)H0+sH1H(s) = (1-s)H_0 + sH_1 as ss goes from 0 to 1 over total time TT. The adiabatic theorem says the system stays in the instantaneous ground state if TT is large compared with 1/gmin21/g_\text{min}^2, where gming_\text{min} is the smallest gap between ground and first excited state along the path. Edward Farhi and colleagues proposed adiabatic quantum computation in 2000–01, and Tadashi Kadowaki and Hidetoshi Nishimori proposed quantum annealing in 1998. Adiabatic computation is equivalent in power to the circuit model. Everything hinges on the gap: for hard problems it can shrink exponentially with size, and so the time grows exponentially. Established

Landau–Zener

Near the minimum gap, two levels look like H=vt2Z+Δ2XH = \tfrac{vt}{2}Z + \tfrac{\Delta}{2}X. Clarence Zener and Lev Landau solved this in 1932: the probability of jumping to the upper level is

Pjump=e−πΔ2/2vP_\text{jump} = e^{-\pi\Delta^2/2v}

Set the gap Δ=\Delta = 1.0 and sweep rate v=v = 1.0. The plate integrates the Schrödinger equation exactly and compares with the formula. Halve the gap and you must sweep four times more slowly for the same success: time scales as 1/Δ21/\Delta^2. Established

Writing problems as Ising models

Annealers accept problems in Ising or QUBO form: minimize ∑Jijzizj+∑hizi\sum J_{ij}z_iz_j + \sum h_iz_i with zi=±1z_i = \pm1. MaxCut becomes ∑(ij)zizj\sum_{(ij)}z_iz_j: every cut edge contributes −1. The plate enumerates all 32 assignments for a 5-vertex graph containing a triangle. The best cut is 5 of 6 edges; a triangle can never be fully cut. The same form encodes scheduling, portfolio choice and, in Part 5, problems such as protein side-chain packing.

Does it help? D-Wave’s annealers have thousands of qubits, but no robust speedup on optimization over the best classical heuristics has been shown. In 2025 Andrew King and colleagues at D-Wave reported a simulation of quantum spin dynamics beyond classical reach; tensor-network groups produced classical simulations within days, and the dispute continues. The same year, Stephen Jordan and colleagues introduced Decoded Quantum Interferometry, with a superpolynomial speedup for a structured problem called optimal polynomial intersection, but none for generic sparse constraint problems. Debated

What you now have

The adiabatic theorem and its gap condition, the Landau–Zener formula, the Ising and QUBO encodings, and the current state of evidence for quantum speedups in optimization.

· · ·

Three questions to carry with you.

What controls adiabatic run time?tap
The minimum gap: T must exceed roughly 1/g_min².
How is MaxCut written as an Ising model?tap
Minimize Σ z_i z_j over edges; each cut edge contributes −1.
Has annealing shown optimization speedup?tap
Not robustly over the best classical heuristics; structured speedups exist for special problems.

And one to work out. With Δ=1\Delta = 1 and v=1v = 1 (units with ℏ=1\hbar = 1), what is the jump probability?

P =

Sources: L. Landau, Phys. Z. Sowjetunion 2, 46 (1932); C. Zener, Proc. R. Soc. A 137, 696 (1932). T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998). E. Farhi et al., Science 292, 472 (2001). T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018). A. D. King et al., Science 388, 199 (2025). S. P. Jordan et al., Nature 646 (2025). Checked by code: exact integration gives 0.043, 0.210, 0.462, 0.670 for v = 0.5, 1, 2, 4, against the formula’s 0.043, 0.208, 0.456, 0.675.

Next · Chapter 126
Quantum simulation overview (detail in Part 5)

Feynman, 1982: "Nature isn't classical, dammit."

Turn the page