Quantum algorithms and lower bounds for convex optimization

Abstract

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an $n$-dimensional convex body using $\tilde{O}(n)$ queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires $\tilde{\Omega }(\sqrt{n})$ evaluation queries and $\Omega (\sqrt{n})$ membership queries.

arXiv comment44 pages, 2 figures. Similar results were independently obtained by Joran van Apeldoorn, Andras Gilyen, Sander Gribling, and Ronald de Wolf <arXiv:1809.00643>

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum gradient descent for linear systems and least squares
• Fast quantum algorithm for numerical gradient estimation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Improvements in Quantum SDP-Solving with Applications
• Convex optimization using quantum oracles
• Efficient Convex Optimization with Membership Oracles
• Quantum Speed-ups for Semidefinite Programming

Cited by in corpus (24)

• Challenges and Opportunities in Quantum Optimization
• Quantum Machine Learning in High Energy Physics
• Biology and medicine in the landscape of quantum advantages
• Quantum SDP-Solvers: Better upper and lower bounds
• Variational Quantum Singular Value Decomposition
• Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Convex optimization using quantum oracles
• Noisy intermediate-scale quantum algorithm for semidefinite programming
• Quantum simulation of real-space dynamics
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Quantum Langevin Dynamics for Optimization
• Quantum algorithms for hedging and the learning of Ising models
• Quantum algorithms for escaping from saddle points
• Small quantum computers and large classical data sets
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Synergies Between Operations Research and Quantum Information Science
• Quantum algorithm for estimating volumes of convex bodies
• Quantum and Classical Algorithms for Approximate Submodular Function Minimization
• A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
• Quantum Legendre-Fenchel Transform
• Quantum Algorithm for Online Convex Optimization
• Quantum query complexity with matrix-vector products