



02027nas a2200133   4500008004100000245005400041210005400095520164000149100002001789700001701809700001401826700001601840856003701856       2018                        eng d00aQuantum adiabatic optimization without heuristics0 aQuantum adiabatic optimization without heuristics3 a<p>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γ&minus;1minlog(γ&minus;1min) with Olog(γ&minus;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&asymp;γ(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&minus;V&minus;1&sum;u,v&isin;V|u&rang;&lang;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&minus;ε)(1&minus;e&minus;1/ε) in time O&tilde;(ε&minus;1[V&minus;&minus;&radic;+(κ&minus;1)2/3V2/3]). This achieves a quantum advantage for all κ, and when κ&asymp;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&tilde;(ε&minus;1[V&minus;&minus;&radic;+(κ&minus;1)2/3V2/3]), even when κ is not known beforehand.</p>1 aJarret, Michael1 aLackey, Brad1 aLiu, Aike1 aWan, Kianna  uhttps://arxiv.org/abs/1810.04686