Optimizing quantum optimization algorithms via faster quantum gradient computation.

András Gilyén, Srinivasan Arunachalam, Nathan WiebeSODA 2017 · DOI · OpenReview

TL;DR

This paper introduces a new quantum algorithm that computes the gradient of a function much faster than previous methods, especially for functions common in quantum optimization. It achieves this by using a novel approach to gradient computation and efficiently converting between different types of quantum oracles, leading to significant speedups for tasks like training quantum machine learning models.

What Problem Does This Paper Address?

Many real-world problems, from machine learning to scientific simulations, rely on optimization. Gradient descent is a powerful classical technique for optimization, but its quantum counterparts have faced challenges. Specifically, computing the gradient of an objective function in a quantum setting can be computationally expensive. While Jordan's algorithm offered a quantum speedup, it required a very precise function evaluation that was often impractical. This paper addresses the need for a more efficient and practical quantum gradient computation method, particularly for objective functions arising from quantum circuits, which often have specific "smoothness" properties.

Methods

The core of this work is an improved quantum gradient computation algorithm. It builds upon Jordan's approach but leverages higher-degree central difference formulas, a technique from calculus, to achieve better accuracy with fewer function evaluations. A key innovation is the efficient conversion between "probability oracles" (common in quantum optimization) and "phase oracles" (more natural for many quantum algorithms), with only a logarithmic overhead. This interconversion is crucial for applying their gradient computation method to a wider range of quantum optimization problems. They also introduce a new lower bound for gradient computation, demonstrating that their algorithm is near-optimal for certain classes of functions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Higher-degree calculus for quantum speedups: Applying advanced calculus techniques (higher-degree central differences) to quantum gradient computation unlocks significant efficiency gains.
  • Oracle interconversion is key: The ability to efficiently switch between probability and phase oracles is a critical enabler for applying quantum gradient computation to diverse quantum optimization problems.
  • Smoothness is common in quantum optimization: Objective functions arising from variational quantum circuits often possess "smoothness" properties that their algorithm exploits for quadratic speedups.
  • Near-optimal gradient computation: The developed algorithm achieves query complexity that is near-optimal for a significant class of smooth functions, up to logarithmic factors.

Key Results

  • The proposed quantum gradient computation algorithm achieves a quadratic improvement in query complexity compared to previous methods for smooth functions, with a complexity of $\tilde{O}(\sqrt{d}/\epsilon)$.
  • For low-degree multivariate polynomials, the algorithm offers an exponential speedup in terms of the dimension $d$ compared to Jordan's algorithm.
  • Efficient subroutines for converting between probability and phase oracles are provided with only logarithmic overhead.
  • The algorithm leads to improved runtimes for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
  • A lower bound of $\Omega(\sqrt{d}/\epsilon)$ is established for gradient computation for certain smooth functions, demonstrating the near-optimality of their approach.

Limitations and Future Work

The authors acknowledge that for non-polynomial functions, achieving the $\sqrt{d}$ scaling requires specific "smoothness" conditions, and they discuss how to handle cases where these conditions are not met. They also suggest future work on generalizing lower bounds for functions with stronger derivative promises and exploring whether quantum techniques can further speed up higher-level derivatives (like the Hessian), potentially leading to quantum analogues of Newton's method. Investigating applications where their polynomial-specific exponential speedups can be leveraged is also a promising direction.

Summary updated

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\rightarrow \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).
BibTeX
@inproceedings{gilyen2017optimizing,
  author = {András Gilyén and Srinivasan Arunachalam and Nathan Wiebe},
  title = {{Optimizing quantum optimization algorithms via faster quantum gradient computation.}},
  booktitle = {SODA},
  year = {2017},
  doi = {10.1137/1.9781611975482.87},
}
Figure