On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

Understand

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.