Convex optimization using quantum oracles

Abstract

We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using $\tilde{O}(1)$ quantum queries to a membership oracle, which is an exponential quantum speed-up over the $\Omega (n)$ membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that $\tilde{O}(n)$ quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: $\Omega (\sqrt{n})$ quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and $\Omega (n)$ quantum separation queries are needed if it does not.

29 pages. Version 4: appears in Quantum, alongside an independent paper with similar results by Shouvanik Chakrabarti, Andrew Childs, Tongyang Li, and Xiaodi Wu <arXiv:1809.01731>

References in corpus (10)

• Strengths and Weaknesses of Quantum Computing
• Negative weights make adversaries stronger
• Fast quantum algorithm for numerical gradient estimation
• Quantum query complexity of some graph problems
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Improvements in Quantum SDP-Solving with Applications
• Quantum algorithms and lower bounds for convex optimization
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Quantum Computation Beyond the Circuit Model
• Efficient Convex Optimization with Membership Oracles

Cited by in corpus (19)

• Quantum Computing for Finance: State of the Art and Future Prospects
• Challenges and Opportunities in Quantum Optimization
• Biology and medicine in the landscape of quantum advantages
• Quantum SDP-Solvers: Better upper and lower bounds
• Variational Quantum Singular Value Decomposition
• Quantum algorithms and lower bounds for convex optimization
• Noisy intermediate-scale quantum algorithm for semidefinite programming
• Quantum simulation of real-space dynamics
• Systems Architecture for Quantum Random Access Memory
• 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
• Quantum algorithm for estimating volumes of convex bodies
• Synergies Between Operations Research and Quantum Information Science
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries
• Quantum Algorithm for Online Convex Optimization
• On Quantum Perceptron Learning via Quantum Search