Vanilla Adiabatic Quantum Optimization Can Have Subexponential Advantage
Source: arxiv.org/abs/2611.24035
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.24035
curl -X POST /api/v1/records/arxiv/2611.24035/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.24035/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'