Quantum adiabatic optimization without heuristics
share
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that γ(s) = Θ(Γ(s)), we provide an algorithm that reliably performs QAO in time Oγ_^-1(γ_^-1) with O(γ_^-1) oracle queries, where γ_ = _s γ(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 T 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 Γ for the problem of finding a vertex m = argmin_u W(u) of the cost function W:V⟶ [0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I - V^-1∑_u,v ∈V|u〉〈 v |, with V = |V|. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m using Γ with probability (1-ϵ)(1-e^-1/ϵ) in time O(ϵ^-1[√(V) + (κ-1)^2/3V^2/3]). This achieves a quantum advantage for all κ, and when κ≈ 1, recovers Grover scaling up to logarithmic factors. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O(ϵ^-1[√(V) + (κ-1)^2/3V^2/3]), even when κ is not known beforehand.
READ FULL TEXT