Adiabatic Quantum Computing

Slow evolution from an easy initial Hamiltonian H_i to a hard problem Hamiltonian H_f. The adiabatic theorem guarantees success if the evolution is slow compared to the minimum spectral gap.

Evolution time T: 50 (units of 1/Δ_min)

Number of qubits n: 4

Energy Spectrum During Adiabatic Evolution

Success Probability vs Evolution Time

0.42

Min gap Δ_min

—

Success prob

—

Speedup vs SA

Adiabatic Theorem

H(s) = (1-s)·H_initial + s·H_final, s = t/T ∈ [0,1]

Adiabatic condition: |⟨1|dH/ds|0⟩| / Δ(s)² ≪ 1/T

P(success) ≈ 1 - (ℏ/Δ_min·T)² [first-order Landau-Zener]

D-Wave uses quantum annealing: non-unitary, finite temperature, but same principle. Minimum gap Δ_min ~ exp(-n) for hard instances (NP-hard in worst case) — where quantum speedup may help via tunneling.