Adiabatic quantum computation: gap closing, Landau-Zener tunnelling, and schedule optimisation
H(s) = −(1−s)Γ·Σσˣᵢ − s·Σ Jᵢⱼσᶻᵢσᶻⱼ, s = t/T
Start in ground state of transverse field (superposition), slowly rotate to problem Hamiltonian. Adiabatic theorem: stay in ground state if Ṡ·|⟨1|∂H/∂s|0⟩| ≪ Δ²(s).
Landau-Zener: P(success) ≈ 1−exp(−π·Δ²_min·T/2). The minimum spectral gap Δ_min controls runtime — for random instances it closes exponentially in N (QMA-hard).
Optimal schedule: spend time ∝ 1/Δ²(s) near the gap (Roland-Cerf protocol).