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.

arXiv comment89 pages, 19 figures (full version)

References in corpus (41)

• Adam: A Method for Stochastic Optimization
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Strengths and Weaknesses of Quantum Computing
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Exponential algorithmic speedup by quantum walk
• Hartree-Fock on a superconducting qubit quantum computer
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• A Variational Perspective on Accelerated Methods in Optimization
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• How to Escape Saddle Points Efficiently
• Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Matrix Completion has No Spurious Local Minimum
• Essentially No Barriers in Neural Network Energy Landscape
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• Sampling Can Be Faster Than Optimization
• Hamiltonian simulation in the low-energy subspace
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Necessary Condition for the Quantum Adiabatic Approximation
• Hamiltonian Simulation in the Interaction Picture
• Quantum algorithms and lower bounds for convex optimization
• Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets
• The Efficient Preparation of Normal Distributions in Quantum Registers
• Convex optimization using quantum oracles
• Semi-classical formula for quantum tunneling in asymmetric double-well potentials
• Optimizing a Polynomial Function on a Quantum Simulator
• How fast do quantum walks mix?
• About small eigenvalues of Witten Laplacian
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)
• Improved Upper Bounds for the Hitting Times of Quantum Walks
• Quantum algorithms for escaping from saddle points
• Every Local Minimum Value is the Global Minimum Value of Induced Model in Non-convex Machine Learning
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• 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