{"id":"arxiv/2611.24035","url":"https://arxiv.org/abs/2611.24035","tags":["quant-ph","cs.CC","math.OC"],"score":0,"title":"Vanilla Adiabatic Quantum Optimization Can Have Subexponential Advantage","domain":"quant-ph","source":"arxiv","authors":["Yufan Zheng"],"reviews":0,"subject":"quant-ph","summary":"We construct a family of objective functions $f \\colon \\{0,1\\}^n \\to \\mathbb{R}$ for which vanilla adiabatic quantum optimization along $H(s) = -(1-s)\\sum_{i=1}^n X_i + s\\sum_x f(x)\\lvert x\\rangle\\!\\langle x\\rvert$ finds the global minimizer in $\\operatorname{poly}(n)$ time, whereas any classical algorithm requires $\\exp(n^{Ω(1)})$ 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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}