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 as goes from 0 to 1 over total time . The adiabatic theorem says the system stays in the instantaneous ground state if is large compared with , where 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 . Clarence Zener and Lev Landau solved this in 1932: the probability of jumping to the upper level is
Set the gap 1.0 and sweep rate 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 . Established
Writing problems as Ising models
Annealers accept problems in Ising or QUBO form: minimize with . MaxCut becomes : 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.
And one to work out. With and (units with ), what is the jump probability?
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.