Optimizing quantum optimization algorithms via faster quantum gradient computation

Abstract

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function $f:{\mathbb{R}}^d\to \mathbb{R}$ by evaluating it at only a logarithmic number of points in superposition. Our algorithm is an improved version of Stephen Jordan's gradient computation algorithm, providing an approximation of the gradient $\nabla f$ with quadratically better dependence on the evaluation accuracy of $f$, for an important class of smooth functions. Furthermore, we show that most objective functions arising from quantum optimization procedures satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension $d$. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function $f$. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

60 pages, 5 figures. Update: stated a separate general theorem about hybrid-method based continuous input lower bound + added reference to work showing optimality of our algorithm

References in corpus (6)

• A Quantum Approximate Optimization Algorithm
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum Computation Beyond the Circuit Model
• A Lower Bound for Quantum Phase Estimation
• Variations on Quantum Adversary
• Quantum computational gradient estimation

Cited by in corpus (43)

• Quantum-assisted quantum compiling
• Stochastic gradient descent for hybrid quantum-classical optimization
• Quantum Algorithm Implementations for Beginners
• Drug design on quantum computers
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Quantum Software Engineering: Roadmap and Challenges Ahead
• Quantum machine learning and quantum biomimetics: A perspective
• Quantum algorithms and lower bounds for convex optimization
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Symmetry enhanced variational quantum spin eigensolver
• Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Convex optimization using quantum oracles
• Quantum Deep Hedging
• Quantum Reinforcement Learning via Policy Iteration
• Optimizing a Polynomial Function on a Quantum Simulator
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum Optimization for Training Quantum Neural Networks
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Quantum Gradient Algorithm for General Polynomials
• Automatic Generation of an Efficient Less-Than Oracle for Quantum Amplitude Amplification
• When Federated Learning Meets Quantum Computing: Survey and Research Opportunities
• Quantum algorithms for escaping from saddle points
• A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
• Parallel Quantum Algorithm for Hamiltonian Simulation
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Random coordinate descent: a simple alternative for optimizing parameterized quantum circuits
• Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation
• A Quantum Search Decoder for Natural Language Processing
• Trade-off between Gradient Measurement Efficiency and Expressivity in Deep Quantum Neural Networks
• Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Cosine series quantum sampling method with applications in signal and image processing
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Simulation-assisted learning of open quantum systems
• Quantum Alphatron: quantum advantage for learning with kernels and noise
• Towards a Pattern Language for Quantum Algorithms
• Quantum Algorithm for Online Convex Optimization
• Expanding the reach of quantum optimization with fermionic embeddings
• Quantum Machine Learning with SQUID