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γ\−1minlog(γ\−1min) with Olog(γ\−1min) 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 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=argminuW(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/3V2/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/3V2/3]), even when κ is not known beforehand.

}, url = {https://arxiv.org/abs/1810.04686}, author = {Michael Jarret and Brad Lackey and Aike Liu and Kianna Wan} }