# (Sub)Exponential Quantum Speedup for Optimization

arXiv: https://arxiv.org/abs/2504.14841 · HTML: https://mlsanity.com/paper/2504.14841/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2025.

## Built on by (most cited first, 2 of 2)

- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Operator-Level Quantum Acceleration of Non-Logconcave Sampling](https://mlsanity.com/paper/2505.05301/) (2025)

## Abstract (arXiv)

We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization. Our result builds on the Gily'en--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing. With a sequence of perturbative reductions, we compile their construction into two standalone objective functions, whose oracles can be directly leveraged by the plain adiabatic evolution and Schr"odinger operator evolution for discrete and continuous optimization, respectively.