Algorithm Zoo · Optimization
Adiabatic Quantum Optimization
Also known as: Quantum annealing, AQO
First described: Farhi, Goldstone, Gutmann, Sipser (theory); D-Wave (hardware), 2000
The problem
Find low-energy states of an Ising Hamiltonian by slowly interpolating from a trivial Hamiltonian.
Prepare ground state of simple H₀ = -Σ Xi. Slowly interpolate H(s) = (1-s)H₀ + s H_problem over time t_f. Adiabatic theorem: ground state stays in ground state if t_f ≫ 1/min_s(gap(H(s)))².
Best classical
Simulated annealing, SDPs, MILP solvers — generally strong.
Quantum complexity
t_f scaling depends on the minimum gap; can be exponential for hard instances.
Our verdict
The longest-running quantum advantage controversy. Twenty-plus years and the field still cannot point to a single optimization problem where adiabatic quantum optimization (or D-Wave annealing) beats simulated annealing on the same hardware budget. The structure of the problem and the gap behavior matter enormously; generic claims should be ignored.
When to use it
- Specific structured problems where the gap has been analyzed and stays open.
- D-Wave hardware with its native Ising connectivity (Chimera, Pegasus, Zephyr) for problems that natively fit.
When not to use it
- Generic combinatorial optimization. Simulated annealing on a laptop typically matches D-Wave on every published benchmark when the embedding cost is included.
- Problems where the gap is known to close exponentially.
Classical baseline
Simulated annealing (Aaronson, Boixo et al. 2013-2015 controversies). Parallel-tempering Monte Carlo. For most published 'quantum advantage' claims on D-Wave, classical methods produce equal or better solutions in less wall-clock time.
Hardware cost
D-Wave Advantage2: 4,400 qubits but with Zephyr connectivity — non-trivial embedding cost. Effective problem size is much smaller than raw qubit count.
Key papers
- Quantum Computation by Adiabatic Evolution ↗
Farhi, Goldstone, Gutmann, Sipser · 2000 · arXiv
- Defining and detecting quantum speedup ↗
Rønnow, Wang, Job, Boixo, Isakov, Wecker, Martinis, Lidar, Troyer · 2014 · Science
Deep-dive tutorials
Last verified: 2026-05-24