On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

Abstract

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.

89 pages, 19 figures (full version)

References in corpus (11)

• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Exponential algorithmic speedup by quantum walk
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• How to Escape Saddle Points Efficiently
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• The Efficient Preparation of Normal Distributions in Quantum Registers
• Semi-classical formula for quantum tunneling in asymmetric double-well potentials
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• Escape saddle points by a simple gradient-descent based algorithm

Cited by in corpus (6)

• Quantum computing for finance
• Quantum Langevin Dynamics for Optimization
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Escaping Local Minima with Quantum Coherent Cooling
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation