# A quantum-classical performance separation in nonconvex optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 29 references that are in the map.
- First posted on arXiv 1 Nov 2023.

## Builds on (most cited first, 3 of 3)

- [On Learning Rates and Schr"odinger Operators](https://mlsanity.com/paper/2004.06977/) (2020)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Quantum simulation of real-space dynamics](https://mlsanity.com/paper/2203.17006/) (2022)

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

- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Quantum Optimization via Gradient-Based Hamiltonian Descent](https://mlsanity.com/paper/2505.14670/) (2025)

## Abstract (arXiv)

In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2d local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any d-dimensional instance from this family using widetildeO(d3) quantum queries to the function value and widetildeO(d4) additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.