WorksPhysics and Astronomy
Vanilla Adiabatic Quantum Optimization Can Have Subexponential Advantage
Abstract
We construct a family of objective functions for which vanilla adiabatic quantum optimization along finds the global minimizer in time, whereas any classical algorithm requires time to do so in the black-box model. Our result is achieved by replacing the linearization technique in an earlier work of Leng et al. (arXiv:2504.14841), which establishes a similar subexponential quantum speedup using a transverse field Ising mixer rather than .