Quantum adiabatic optimization without heuristics

Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Gamma such that γ_min = Thetaleft(minsGamma(s)right), we provide an algorithm that reliably performs QAO in time Oleft(γ_min-1right) with Oleft(log(γ_min-1)right) oracle queries, where γ_min = mins γ(s). Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that |dH/ds| ≈ γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Gamma for the problem of finding the minimum point m = argminu W(u) of the cost function W:Vlongrightarrow [0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I - |V|-1sumu,v ∈ Vverturanglelanglevvert. Requiring only that W have a constant lower bound on its spectral gap and upper bound kappa on its spectral ratio, our QAO algorithm returns m with probability (1-ε)(1-e-1/ε) in time widetildeO(ε-1[√|V| + (kappa-1)2/3|V|2/3]). This achieves a quantum advantage for all kappa, and recovers Grover scaling up to logarithmic factors when kappa ≈ 1. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime widetildeO(ε-1[√|V| + (kappa-1)2/3|V|2/3]) even when kappa is not known beforehand.