# On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 79 references that are in the map.
- First posted on arXiv 29 Sep 2022.

## Builds on (most cited first, 30 of 39)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [Essentially No Barriers in Neural Network Energy Landscape](https://mlsanity.com/paper/1803.00885/) (2018)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks](https://mlsanity.com/paper/1710.11029/) (2017)
- [On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)](https://mlsanity.com/paper/2102.12470/) (2021)
- [Optimization for deep learning: theory and algorithms](https://mlsanity.com/paper/1912.08957/) (2019)
- [Understanding the Acceleration Phenomenon via High-Resolution Differential Equations](https://mlsanity.com/paper/1810.08907/) (2018)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets](https://mlsanity.com/paper/1906.06247/) (2019)
- [On Connected Sublevel Sets in Deep Learning](https://mlsanity.com/paper/1901.07417/) (2019)
- [Sharp Analysis for Nonconvex SGD Escaping from Saddle Points](https://mlsanity.com/paper/1902.00247/) (2019)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks](https://mlsanity.com/paper/1912.10095/) (2019)
- [On Learning Rates and Schr"odinger Operators](https://mlsanity.com/paper/2004.06977/) (2020)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [On the Optimization Landscape of Tensor Decompositions](https://mlsanity.com/paper/1706.05598/) (2017)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [On the Local Minima of the Empirical Risk](https://mlsanity.com/paper/1803.09357/) (2018)
- [Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles](https://mlsanity.com/paper/2111.13263/) (2021)
- [Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing](https://mlsanity.com/paper/1601.03030/) (2016)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)

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

- [FOCUS: First Order Concentrated Updating Scheme](https://mlsanity.com/paper/2501.12243/) (2025)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [A quantum-classical performance separation in nonconvex optimization](https://mlsanity.com/paper/2311.00811/) (2023)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [Quantum Optimization via Gradient-Based Hamiltonian Descent](https://mlsanity.com/paper/2505.14670/) (2025)
- [Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent](https://mlsanity.com/paper/2604.13022/) (2026)

## Abstract (arXiv)

Classical algorithms are often not effective for solving nonconvex optimization problems where local minima are separated by high barriers. In this paper, we explore possible quantum speedups for nonconvex optimization by leveraging the global effect of quantum tunneling. Specifically, we introduce a quantum algorithm termed the quantum tunneling walk (QTW) and apply it to nonconvex problems where local minima are approximately global minima. We show that QTW achieves quantum speedup over classical stochastic gradient descents (SGD) when the barriers between different local minima are high but thin and the minima are flat. Based on this observation, we construct a specific double-well landscape, where classical algorithms cannot efficiently hit one target well knowing the other well but QTW can when given proper initial states near the known well. Finally, we corroborate our findings with numerical experiments.