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.

44 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 (3)

• Quantum algorithm for solving linear systems of equations
• Convex optimization using quantum oracles
• Efficient Convex Optimization with Membership Oracles

Cited by in corpus (23)

• Challenges and Opportunities in Quantum Optimization
• Quantum Machine Learning in High Energy Physics
• Biology and medicine in the landscape of quantum advantages
• 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
• Small quantum computers and large classical data sets
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Quantum algorithms for hedging and the learning of Ising models
• Quantum algorithms for escaping from saddle points
• 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