Quantum Annealing
Adiabatic optimization via transverse field Ising model — gap and tunneling
Quantum Annealing (Kadowaki-Nishimori 1998): H(s) = −(1−s)Γ·Σ_i σ_i^x − s·Σ_{ij} J_{ij}·σ_i^z·σ_j^z where s = t/T goes 0→1. The initial ground state (all spins in x-basis) evolves adiabatically to the Ising ground state. The adiabatic theorem requires T >> 1/Δ_min², where Δ_min is the minimum spectral gap. In frustrated spin glasses, Δ_min → 0 exponentially with N, setting the fundamental hardness of quantum annealing. Quantum tunneling can bypass classical energy barriers.