Quantum algorithms for escaping from saddle points

Abstract

We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function $f:{\mathbb{R}}^n\to \mathbb{R}$, our quantum algorithm outputs an $\epsilon$-approximate second-order stationary point using $\tilde{O}({\log }^2(n)/{\epsilon }^{1.75})$ queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with $\tilde{O}({\log }^6(n)/{\epsilon }^{1.75})$ queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of $\log n$ and matches its complexity in terms of $1/\epsilon$. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the improvement in the quantum query complexity with $\log n$ factors for escaping from saddle points. We also show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our theoretical findings.

arXiv comment47 pages, 5 figures. Accepted by Quantum

References in corpus (21)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Gaussian Quantum Information
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Efficient quantum algorithms for simulating sparse Hamiltonians
• A Theory of Trotter Error
• Efficient Simulation of Quantum Systems by Quantum Computers
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A quantum-inspired classical algorithm for recommendation systems
• A Geometric Analysis of Phase Retrieval
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• The statistics of critical points of Gaussian fields on large-dimensional spaces
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Fast quantum algorithm for numerical gradient estimation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum SDP-Solvers: Better upper and lower bounds
• Quantum algorithms and lower bounds for convex optimization
• Convex optimization using quantum oracles

Cited by in corpus (7)

• Biology and medicine in the landscape of quantum advantages
• Quantum simulation of real-space dynamics
• Quantum Langevin Dynamics for Optimization
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation