



@article {2281,
	title = {Quantum adiabatic optimization without heuristics},
	year = {2018},
	abstract = {<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>},
	url = {https://arxiv.org/abs/1810.04686},
	author = {Michael Jarret and Brad Lackey and Aike Liu and Kianna Wan}
}
