betaFeedback

WorksPhysics and Astronomy

Vanilla Adiabatic Quantum Optimization Can Have Subexponential Advantage

Abstract

We construct a family of objective functions f ⁣:{0,1}n→Rf \colon \{0,1\}^n \to \mathbb{R} for which vanilla adiabatic quantum optimization along H(s)=−(1−s)∑i=1nXi+s∑xf(x)∣x⟩ ⁣⟨x∣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 poly⁡(n)\operatorname{poly}(n) time, whereas any classical algorithm requires exp⁡(nΩ(1))\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 −∑i=1nXi-\sum_{i=1}^n X_i.

Paper details

vlnc:W_a8h5dzku
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…