PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén, Srinivasan Arunachalam, Nathan Wiebe

arXiv:1711.00465v3quant-phcs.CC

TL;DR

Quantum gradient computation for continuous optimization is limited by the cost and precision of objective-function evaluations, especially with probability-oracle access. The paper introduces a logarithmic-point quantum gradient algorithm with improved precision dependence, proves near-optimality for certain smooth functions, and applies oracle conversion to quantum optimization protocols.

  • Problem

    Quantum optimization procedures often use probability oracles, while existing gradient methods can require prohibitively precise function evaluations or stronger oracle models.

  • Method

    The paper combines an improved quantum gradient algorithm, probability-phase oracle interconversion, amplitude estimation, and quantum minimum finding for gradient-based optimization.

  • Results

    The algorithm achieves quadratic improvements for an important class of smooth functions, is near-optimal up to poly-logarithmic factors for some smooth functions, and can yield exponential dimension speedups for low-degree polynomials.

  • Takeaways & Limitations

    The tools improve quantum optimization protocols for applications including machine learning and quantum chemistry simulation, with oracle conversion enabling the applications.

  • Takeaways & Limitations

    Grover-based methods may require running gradient updates for the largest possible iteration count when convergence times vary, and probability-to-phase conversion loses information because probabilities are squared amplitudes.

Abstract

from arXiv · show

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).

1 Introduction

The paper develops quantum gradient-based optimization methods for continuous problems, addressing the difficulty of applying advanced quantum techniques to generic real-world objectives. Its approach improves gradient-computation complexity and supports quantum speedups for optimization protocols.

  • Quantum optimization has been less developed for continuous problems than for several other computational tasks, while generic objectives often fail the requirements of advanced quantum techniques.
  • The paper improves quantum gradient computation for gradient-based optimization, reducing query and gate complexity quadratically under reasonable continuity assumptions.
  • The framework builds on Jordan’s gradient algorithm and relates to prior quantum-state-based approaches for gradient descent and polynomial optimization.
  • Probability-oracle access models the sampling-based objective evaluations common in quantum optimization procedures.
  • Quantum gradient descent combines amplitude estimation, quantum minimum finding, and an improved gradient algorithm to reduce complexity across almost all parameters except the iteration count T.

1.4 Conversion between probability and phase oracles

The paper addresses the mismatch between probability oracles common in quantum optimization and phase oracles used by many quantum techniques. It provides logarithmic-overhead interconversion and an improved gradient procedure based on high-degree central differences.

  • Many quantum optimization procedures use probability oracles, whereas the paper’s quantum techniques more naturally use phase oracles.
  • O(log(1/ε)) queries to a probability oracle suffice to simulate a phase oracle with ε precision using LCU techniques.
  • The conversion enables interchangeable use of probability and phase oracles, supporting applications beyond the paper’s immediate optimization setting.
  • Jordan’s algorithm uses one highly precise binary-oracle evaluation, whereas the new method uses multiple lower-precision evaluations suited to probability-oracle access.
  • High-degree central-difference formulas evaluate an analytic function at logarithmically many points, followed by a d-dimensional quantum Fourier transform that outputs a classical approximate gradient.
  • For degree-k multivariate polynomials, the algorithm has query complexity e O(k log(d)/ε), yielding an exponential dimension speedup when k = O(log(d)).

1.6 Smoothness of probability oracles

The paper shows that probability oracles from typical parametrized quantum circuits satisfy the smoothness assumptions required for its gradient algorithm. It also establishes near-optimal lower bounds for a class of smooth functions.

  • Probability oracles in typical quantum optimization protocols represent measurement probabilities of projectors applied to parametrized circuit outputs.
  • Under the stated circuit conditions, the objective probability is analytic and all partial derivatives are bounded in magnitude by 1.
  • The paper’s lower-bound theorem shows that its gradient-computation algorithm is optimal up to poly-logarithmic factors for a specific class of smooth functions.
  • The lower-bound construction uses smooth functions whose gradients identify the functions, making gradient approximation at least as hard as distinguishing their phase oracles.
  • An eΩ(d/ε) lower bound also applies in the probability-oracle model after efficient probability-to-phase conversion.

1.8 Significance of our improvement for applications

The paper’s improvement is most relevant when objectives are evaluated by sampling, where function precision can dominate runtime. In that setting, the new algorithm offers useful quadratic scaling improvements while generic smooth functions impose a super-quadratic speedup limit.

  • Arithmetic function evaluation typically has poly-logarithmic precision dependence, whereas sampling-based evaluation usually has polynomial dependence on reciprocal precision.
  • For arithmetically evaluated functions, the cheap gradient principle makes gradient computation typically comparable to function evaluation, limiting Jordan’s speedup to a constant factor.
  • Jordan’s precision requirements can be prohibitive in sampling-based applications such as VQE and QAOA.
  • For generic smooth functions in the sampling case, super-quadratic speedups for ε-accurate gradient computation are impossible, ignoring polylogarithmic factors.
  • Table 2 compares quantum and classical query complexities for smooth and degree-k polynomial functions under probability-oracle access.
  • The optimized semi-classical method uses quantum amplitude estimation for function values and high-order central differences for coordinate-wise classical gradients.

1.9 Applications

The paper applies its quantum gradient-descent framework to VQE, QAOA, and quantum auto-encoding, positioning these as representative quantum optimization and machine-learning tasks.

  • Applications: The framework targets VQE, QAOA, and quantum auto-encoding as three application problems.VQE estimates Hamiltonian eigenvalues, QAOA tunes parametrized states for objective minimization, and auto-encoders learn low-dimensional data representations.
  • VQE: VQE varies a parametrized ansatz to minimize the expected energy of a quantum state.
  • QAOA: QAOA tunes parameters in a parametrized state family to minimize an objective that can encode a combinatorial optimization problem.Constraint-violation counts provide one example of such an objective.
  • QAOA: After normalization and standard techniques, QAOA's expectation-value objective can be mapped to a measurement probability, making it algorithmically equivalent to VQE.
  • Quantum auto-encoding: Quantum auto-encoders seek low-dimensional representations that approximately preserve computations on high-dimensional data.

2 Organization of the paper and preliminaries

The paper organizes its development around quantum optimization models, oracle conversion, gradient computation, lower bounds, and applications, while introducing notation for higher-order calculus and central differences.

  • Organization: The paper proceeds from a generic optimization model and classical gradient descent to oracle conversion, quantum gradient computation, query lower bounds, and applications.
  • Notation: The notation defines vector norms, matrix operator norms, standard basis vectors, index sets, and conventions for 0^0 and N_0.
  • Preliminaries: Higher-order calculus is introduced through index-sequences, products of indexed vector components, and iterated partial derivatives.
  • Preliminaries: An analytic function is introduced as a class of functions satisfying the paper's stated analytic condition.
  • Preliminaries: Directional derivatives are defined by differentiating a one-parameter restriction of a multivariate function along a direction.
  • Preliminaries: Central difference formulas use polynomial interpolation to approximate directional derivatives and thereby gradients.The paper defines degree-2m central-difference approximations and proves generic approximation-error bounds in Appendix A.

3 A generic model of quantum optimization algorithms

The generic model represents tunable quantum circuits with real or quantum parameters and optimizes a measurement probability using gradient ascent, amplitude estimation, Grover search, and improved gradient computation.

  • Generic model: Quantum optimization circuits combine state preparation, tunable and fixed gates, and verification that marks success through an auxiliary-qubit measurement.
  • Generic model: Parameters can be classically set or represented by qubits, with quantum parameters enabling quantum optimization techniques at the cost of extra qubits and controlled gates.
  • Gradient ascent: The optimization objective is a measurement probability, and gradient ascent iteratively updates parameters toward a local maximum from multiple random starting points.
  • Quantum speedups: Quantum amplitude estimation reduces the circuit uses needed to estimate p(x) to error ε from Ω(1/ε^2) classical repetitions to O(1/ε).
  • Quantum speedups: Quantum maximum finding can reduce the repetitions over N random starting points, but reversibility may require retaining all visited points and increasing qubit usage.
  • Quantum speedups: Grover-based optimization can require running updates for the largest possible number of gradient steps because different starting points reach local maxima at different times.
  • Quantum speedups: The paper's gradient-computation method gives a quadratic speedup in the number d of control parameters, with smaller qubit overhead than the preceding Grover-based speedup.

4 Interconvertibility of oracles

The paper develops probability and phase oracle models and uses LCU techniques to convert between them with logarithmic precision overhead, under conditions needed for the reverse conversion.

  • Oracle models: The objective is represented by a probability oracle whose final-qubit measurement probability is p(x), while phase oracles encode function values directly as phases.
  • Oracle models: Binary-oracle conversion from a probability oracle requires O(1/ε) oracle invocations to obtain log(1/ε) bits of precision.
  • Oracle conversion: The paper directly converts probability oracles to phase oracles with LCU techniques, avoiding an analogue→digital→analogue route and introducing logarithmic precision overhead.
  • Grover-operator geometry: The Grover operator acts as a rotation by angle 2θ(x) on a two-dimensional invariant subspace, with eigenvalues e^±2iθ(x).
  • Oracle conversion: The reverse conversion uses O(log(1/ε)/δ) phase-oracle invocations when probabilities lie in [δ,1−δ], making the oracle models essentially equivalent under that condition.
  • Oracle conversion: The probability-to-phase conversion loses information because probabilities encode squared amplitudes, and the required lower bound away from zero reflects this limitation.

5 Improved quantum gradient computation algorithm

The paper improves Jordan’s quantum gradient algorithm by directly using central-difference formulas and higher-order smoothness, achieving near-linear precision dependence while retaining square-root dimension scaling. The resulting algorithm is optimal up to logarithmic factors for a class of smooth functions and can yield exponential dimension speedups for low-degree polynomials.

  • Jordan’s algorithm: Jordan’s algorithm estimates a d-dimensional gradient from one function evaluation by encoding local function values into phases and applying an inverse Fourier transform.The classical finite-difference approach uses d + 1 evaluations, whereas Jordan’s method evaluates a superposition of grid points.
  • Improvement over Jordan: The improved method directly uses central-difference formulas on a symmetric grid rather than treating the grid superposition as an analogue of central differencing.Central differences cancel the quadratic correction term, improving the approximation structure.
  • Complexity: The algorithm achieves essentially linear dependence on 1/ε and rigorously establishes square-root dependence on d under reasonable derivative assumptions.This improves Jordan’s quadratic precision dependence and addresses possible dimension dependence from higher-order Taylor terms.
  • Optimality: The query complexity is optimal up to logarithmic factors for a specific class of smooth functions.The paper proves a matching lower bound up to log factors.
  • Assumptions: The analysis assumes phase-oracle access and notes that finite-domain boundaries can increase complexity when the evaluation point lies too close to the boundary.The stated result evaluates the function within a finite ball around the target point, while applications are assumed to permit sufficiently distant evaluations.
  • Polynomial objectives: For multivariate polynomials of degree k = O(log(d)), the method provides an exponential speedup in dimension compared with Jordan’s algorithm.Choosing m = ⌈k/2⌉ makes the relevant higher-derivative bound B equal to zero.

6 Lower bounds on gradient computation

The paper establishes lower bounds for quantum gradient computation by reducing accurate gradient estimation to distinguishing carefully constructed phase oracles. These bounds match the algorithmic upper bounds up to logarithmic factors for broad classes of smooth functions.

  • Optimality: The resulting lower bound matches the algorithm’s upper bound up to logarithmic factors for a specific class of smooth functions.The paper states that this makes the gradient-computation algorithm essentially optimal for a large class of problems.
  • Oracle models: The lower bound also transfers to probability-oracle models because probability oracles can be simulated with a logarithmic number of phase-oracle queries.A range transformation places the hard functions inside a valid probability range for the conversion argument.
  • Hybrid method: A hybrid-method theorem bounds the number of phase-oracle queries needed to distinguish one oracle from a finite family of alternatives.The framework also permits controlled phase-oracle queries and inverse oracle calls.
  • Proof design: The paper notes that a search-style reduction is unsuitable because phase oracles are strong enough that gradient computation can solve exact counting.This explains why the lower-bound proof uses phase-oracle distinguishability instead of a direct search reduction.
  • Hard-function construction: The lower-bound strategy constructs smooth functions whose gradients identify the underlying phase oracle, so ε-accurate gradient computation must distinguish those oracles.The hard family includes the zero function and functions with gradients differing in individual coordinates.

7 Applications

The paper applies its gradient-computation methods to VQE, QAOA, and quantum autoencoder training by expressing objectives through measurement probabilities. For VQE, a Hadamard-test circuit converts ground-state energy expectations into probabilities, enabling phase-oracle simulation and quadratic improvements under the stated oracle-cost conditions.

  • Applications: The applications reduce VQE and QAOA optimization to probability maximization, while quantum autoencoder training uses a related formalism.For each application, the gradient method yields a quadratic speedup in the dimension.
  • Variational quantum eigensolvers: VQE varies a parameterized ansatz to minimize an expected Hamiltonian energy, which is mapped to a measurement probability.This makes the objective accessible to the paper’s gradient-computation methods.
  • Variational quantum eigensolvers: The VQE verifier uses a Hadamard test whose probability of measuring 1 is 1/2 − ⟨ψ(x)|H|ψ(x)⟩/2.The construction uses the state-preparation and Hamiltonian-oracle components to produce the required probability oracle.
  • Variational quantum eigensolvers: The probability oracle can be converted into a phase oracle with O(log(1/δ)) applications of the underlying unitary and O(1) fundamental queries under the stated construction.The unitary requires O(1) fundamental queries to selectH and prepareW.
  • Variational quantum eigensolvers: The resulting gradient procedure gives a quadratic improvement when selectH and prepareW are sub-dominant to state preparation costs.The comparison assumes constant error in the infinity norm and compares against high-degree gradient methods using empirically estimated gradients.
  • QAOA: QAOA has the same optimization structure as VQE for this analysis, differing mainly in the parameterization chosen for the state.Its objective can be represented by a Hermitian operator associated with the optimization problem.
  • Quantum autoencoders: For quantum autoencoders, the method applies to pure n-qubit inputs mapped to k-qubit outputs and uses unitary representations of the encoding and decoding channels.The paper shows that this optimization problem can also be accelerated by its gradient-computation algorithm.

8 Conclusion and future research

The paper introduces a quantum gradient method that is nearly query-optimal for a class of smooth functions and improves approximation-accuracy scaling over Jordan’s algorithm. It also enables polynomial speedups in applications, while leaving broader lower bounds and higher-order optimization methods for future work.

  • Main conclusions: The new gradient method is asymptotically optimal up to logarithmic factors for certain smooth functions under max-norm error.Its analysis concerns the number of queries needed to estimate the gradient within fixed error.
  • Main conclusions: The high-degree interpolation approach quadratically improves query-complexity scaling with approximation quality over Jordan’s algorithm.For low-degree multivariate polynomials, it can provide exponential speedups over Jordan’s or classical algorithms.
  • Applications and future work: The paper applies the method to machine learning and quantum chemistry simulation through phase–probability oracle interconversion.These applications produce polynomial speedups, while exponential-speedup applications for low-degree polynomials remain an open direction.
  • Limitations and future work: Generalizing lower bounds to functions with stronger high-order derivative promises remains unresolved.The paper also identifies higher-level stochastic optimization and Hessian computation as future research directions.

A Error bounds on central difference formulas

The appendix develops error bounds for central-difference formulas and uses them to upper-bound quantum gradient-computation complexity under bounded higher derivatives or analyticity assumptions.

  • Method: The error analysis combines Algorithm 2 with central differences and higher-dimensional calculus to bound gradient-computation query complexity.The appendix derives the needed finite-difference bounds and applies them to quantum gradient computation.
  • Coefficient bounds: Numerical experiments show that the relevant coefficient quantity is lower bounded by (m/e)^2m, indicating that the proven upper bound is qualitatively right.This comparison concerns the important case k = 2m.
  • Bounded derivatives: The central-difference lemma derives the approximation by combining a Taylor expansion, Lagrange interpolation, and a bound on the difference between the derivative and the finite-difference formula.The construction uses an order-(2m) Taylor polynomial and a (2m)-th central difference formula.
  • Bounded derivatives: Theorem 23 computes an approximate gradient from phase-oracle access when f is (2m + 1)-times differentiable with bounded higher derivatives.It guarantees an approximation g satisfying ∥g −∇f(0)∥∞≤ε with stated success probability.
  • Dimension dependence: Choosing m = log(d/ε) yields an overall query-complexity upper bound under the strongest regularity assumptions considered.The resulting bound achieves the desired O(1/ε)-scaling in ε but does not capture the desired dependence on d because of a loose bound on B.
  • Analytic functions: Theorem 24 treats analytic functions and establishes a bound that holds for all but a 1/1000 fraction of points in the relevant grid.Its proof uses the multidimensional Taylor series and central-difference formulas, with the exceptional fraction stated explicitly.

B Interconversion between phase and probability oracles

This section develops efficient conversions between phase and probability oracles, using polynomial approximation and amplitude-amplification techniques while accounting for boundary effects in the probability range.

  • Interconversion: Phase and probability oracles can be converted back and forth with logarithmic overhead in the precision when probabilities are bounded away from 0 and 1.This also supports implementing generalized fractional queries using a phase oracle.
  • Phase to probability: Phase-to-probability conversion uses O(log(1/ε)/δ) controlled phase-oracle invocations when p maps into [δ,1 −δ].The construction implements a probability oracle with logarithmic precision overhead and inverse dependence on the distance from the boundaries.
  • Phase to probability: The conversion method approximates the required amplitude transformation with a Taylor-series representation and linear-combination-of-unitaries techniques.The phase is shifted before implementing the amplitude transformation, and the approximation coefficients can be computed efficiently classically.
  • Boundary effects: The conversion loses information when p is close to 0 or 1 because probability encodes the squared amplitude.The section notes that amplitude-to-phase conversion could avoid this loss but introduces additional care for complex amplitudes.

C Robust oblivious amplitude amplification

The section generalizes robust oblivious amplitude amplification and analyzes it through invariant two-dimensional subspaces arising from pairs of orthogonal projectors.

  • Generalized amplification: The appendix introduces a generalized robust oblivious amplitude-amplification procedure with improved constants in its error bounds.The construction begins from Jordan’s theorem on orthogonal projectors.
  • Projector decomposition: Jordan’s theorem decomposes the Hilbert space into orthogonal one- and two-dimensional subspaces associated with the projectors.This decomposition supplies the subspaces used to analyze the amplification operator.
  • Rotation picture: The 2D subspace lemma shows that the product of two reflected projectors acts as a rotation by angle 2θ on an invariant subspace.The invariant subspace is spanned by the target and orthogonal components of the state produced by W.
  • Robustness conditions: The robust analysis applies when the relevant projector overlaps remain bounded away from zero and one, allowing approximate amplitude amplification under controlled error.The stated conditions constrain the norm of the projected state to a multiplicative interval around sin(θ).
Loading 1711.00465v3…