PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms

Aram Harrow, John Napp

arXiv:1901.05374v1quant-phmath.OC

TL;DR

Variational algorithms often rely on noisy objective-function measurements, motivating derivative-free optimization despite difficult stochastic, generally nonconvex landscapes. This paper introduces a black-box framework for analytic gradient measurements, proving faster convergence in a toy problem and deriving convex-region query-cost bounds for stochastic gradient and mirror descent.

  • Problem

    Quantum measurement randomness gives variational algorithms stochastic access to objective functions, while derivative-free optimization can converge much more slowly than noiseless optimization.

  • Method

    The paper defines a black-box variational setting and combines analytic gradient measurements with stochastic gradient descent or stochastic mirror descent, using classical stochastic-optimization results for convex regions.

  • Results

    For a simple observable family, stochastic gradient descent with analytic gradient measurements outperforms every zeroth-order strategy, while convex-region query bounds are obtained for both SGD and SMD.

  • Takeaways & Limitations

    Low-depth gradient measurements can provide substantially faster convergence than objective-function measurements in some variational-optimization settings.

  • Takeaways & Limitations

    The rigorous bounds assume a trusted convex region containing an optimum and, for strong-convexity improvements, a good estimate of the strong-convexity parameter.

Abstract

from arXiv · show

A broad class of hybrid quantum-classical algorithms known as "variational algorithms" have been proposed in the context of quantum simulation, machine learning, and combinatorial optimization as a means of potentially achieving a quantum speedup on a near-term quantum device for a problem of practical interest. Such algorithms use the quantum device only to prepare parameterized quantum states and make simple measurements. A classical controller uses the measurement results to perform an optimization of a classical function induced by a quantum observable which defines the problem. While most prior works have considered optimization strategies based on estimating the objective function and doing a derivative-free or finite-difference-based optimization, some recent proposals involve directly measuring observables corresponding to the gradient of the objective function. The measurement procedure needed requires coherence time barely longer than that needed to prepare a trial state. We prove that strategies based on such gradient measurements can admit substantially faster rates of convergence to the optimum in some contexts. We first introduce a natural black-box setting for variational algorithms which we prove our results with respect to. We define a simple class of problems for which a variational algorithm based on low-depth gradient measurements and stochastic gradient descent converges to the optimum substantially faster than any possible strategy based on estimating the objective function itself, and show that stochastic gradient descent is essentially optimal for this problem. Importing known results from the stochastic optimization literature, we also derive rigorous upper bounds on the cost of variational optimization in a convex region when using gradient measurements in conjunction with certain stochastic gradient descent or stochastic mirror descent algorithms.

1 Introduction

Variational algorithms shift quantum state preparation and measurement into a classical optimization loop, but stochastic measurement access can make optimization difficult. This paper formalizes the setting and shows that analytic gradient measurements can substantially reduce query complexity for a simple problem class.

  • Motivation: Quantum measurement randomness gives the outer loop stochastic access to f rather than direct function values, and can change convergence from logarithmic to polynomial in 1/ε.This motivates comparing objective-function measurements with direct gradient measurements.
  • Convex optimization bounds: General convex-region bounds combine analytic gradient measurements with stochastic gradient descent or stochastic mirror descent and depend on precision, dimension, observable and pulse-generator parameters, and strong convexity.The analysis records bounds for both Euclidean SGD and l1-based SMD.
  • Limitations: The reported upper bounds are promise-setting worst-case results requiring a trusted convex region containing an optimum and, for strong-convexity bounds, a good estimate of the strong-convexity parameter.The authors note that these conditions may not hold in practice and that empirical methods can outperform worst-case bounds.
  • Query complexity separation: Analytic gradient measurements with stochastic gradient descent require O(n^2/ε) queries, versus an Ω(n^3/ε^2) lower bound for zeroth-order methods on the toy family H^ε_n.The separation applies to precision 0 < ε < Θ(n) and queries near the optima.
  • Query complexity separation: For the toy observables, even algorithms using derivatives of any order require Ω(n^2/ε) queries, making stochastic gradient descent essentially optimal.Stochastic mirror descent with an l1 geometry is only O(log n) worse than SGD.

1.3 Related work

The paper studies low-depth gradient measurements in variational algorithms and situates its results within stochastic optimization and derivative-free optimization. It introduces a black-box framework tailored to variational quantum algorithms.

  • 1.3 Related work: The paper focuses on low-depth gradient measurements, which provide unbiased but potentially noisy gradient estimates, while contrasting them with an alternative higher-precision method requiring greater resources.The alternative approach offers better performance for precise gradient estimation but has additional resource requirements.
  • 1.3 Related work: The separation result resembles prior lower bounds for derivative-free stochastic convex optimization, but those classical results do not directly apply to variational quantum algorithms.The paper attributes the difference to the quantum-observable-induced stochastic optimization setting.
  • 1.3 Related work: The paper is organized around preliminaries, a black-box oracle formulation, general query-cost upper bounds, and a parameterized separation construction.The appendices provide background on first-order stochastic convex optimization and notation.

2 Preliminaries

The preliminaries define the variational ansatz, objective and measurement conventions, and the stochastic optimization results used later. They also review upper bounds for gradient-based and zeroth-order convex optimization.

  • 2 Preliminaries: Variational states use a pulse-based ansatz built from an easy-to-prepare starting state, parameters in a feasible set, and Hermitian pulse generators.Each factor is called a pulse, and the feasible set contains the allowed parameter vectors.
  • 2 Preliminaries: The objective is a classical function induced by a Hermitian objective observable, while the quantum device is assumed to measure Pauli operators.The paper establishes the measurement model used for the later sampling-oracle analysis.
  • 2 Preliminaries: The paper fixes conventions for qubits, vector norms, dual norms, indexing, and logarithms, and collects notation and parameters in Table 3.These conventions support the norm-dependent stochastic optimization bounds.
  • 2 Preliminaries: Upper bounds in convex regions combine classical stochastic optimization guarantees with quantum sampling strategies for estimating gradients.The analysis uses stochastic gradient descent and stochastic mirror descent results under convexity and strong-convexity assumptions.
  • 2 Preliminaries: The stochastic gradient oracle is unbiased and has bounded second moments, with optimization guarantees stated for convex and strongly convex feasible regions.The assumptions include a closed convex feasible set and a minimizer of the objective.
  • 2 Preliminaries: The reviewed stochastic mirror descent results cover Euclidean and l1 setups, including strongly convex objectives with norm-specific assumptions.The relevant bounds depend on the geometry of the feasible set and the chosen norm.
  • 2 Preliminaries: Known stochastic zeroth-order bounds are generally weaker than first-order bounds and yield convergence rates for noisy objective-value access under convexity and Lipschitz assumptions.The reviewed results also imply query requirements for achieving a target expected precision.
  • 2 Preliminaries: The paper notes that zeroth-order optimization requires a finite number of queries to reach expected precision ǫ, while other derivative-free bounds apply only in less relevant or specialized settings.These results provide the comparison class for the paper’s variational optimization analysis.

3 Black-box formulation

The black-box formulation hides the objective observable behind a sampling oracle so query complexity can be studied independently of detailed knowledge of the objective. The oracle supports zeroth-order, gradient, and higher-order sampling for variational ansätze.

  • 3 Black-box formulation: The black-box model addresses the trivial classical-simulation loophole by restricting the outer loop to oracle access rather than direct knowledge of the objective observable.This framework is intended to capture realistic general-purpose optimization algorithms.
  • 3 Black-box formulation: The outer loop receives an oracle encoding an objective observable from a promised family and seeks an approximate optimum using as few queries as possible.This defines the query-complexity problem studied in the paper.
  • 3 Black-box formulation: The sampling oracle accepts a parameterization, parameter vector, and coordinate multiset, then returns an unbiased random variable for the corresponding derivative order.The zeroth-order output estimates f(θ), while larger coordinate multisets specify higher-order sampling.
  • 3.1 Zeroth-order sampling: For zeroth-order sampling, the oracle decomposes the observable into Pauli products, samples a term according to coefficient weights, measures it, and rescales the ±1 outcome.The resulting estimator is unbiased and bounded by the normalization factor.
  • 3.2 Analytic gradient measurements: Traditional variational optimization obtains noisy objective values, whereas analytic gradient measurements directly extract information about ∇f(θ) from corresponding quantum observables.The paper treats these measurements as first-order oracle access.
  • 3.2 Analytic gradient measurements: Each derivative term is expanded using Pauli decompositions of the pulse generators and objective observable, allowing linearity-based measurement of the gradient components.The construction reduces gradient estimation to measurable Pauli-based quantities.
  • 3.2 Analytic gradient measurements: A generalized Hadamard test estimates the required imaginary overlaps using an ancilla, controlled operations, pulse sequences, and a final Pauli-Y measurement.The paper notes that alternative analytic-gradient methods use similar quantum resources, with some avoiding controlled-Pauli gates.
  • 3.2 Analytic gradient measurements: The gradient can be represented as expectations of Hermitian operators derived from pulse generators, the objective observable, and commutators.This representation enables coordinate-wise gradient estimation through Pauli decompositions and quantum measurements.

4 General upper bounds for variational algorithms in a convex region

The paper derives query-cost upper bounds for low-depth gradient measurements combined with stochastic gradient or mirror descent in convex regions. It also compares these bounds with derivative-free optimization and identifies settings where the choice of norm and optimizer changes scaling.

  • 4.1 Gradient estimators from oracle queries: Gradient estimators from Algorithms 3 and 4 are unbiased, with Algorithm 3 fixing the estimator norm and Algorithm 4 designed for reduced ∞-norm in SMD.Algorithm 3 uses l1 sampling for SGD, while Algorithm 4 uses l2 sampling for SMD.
  • 4.2 Upper bounds: Projected SGD and SMD yield convex and strongly convex query-cost bounds when first-order oracle outputs are used with appropriate stepsizes and mirror maps.The bounds are stated for Euclidean and l1 geometries, respectively.
  • 4.2 Upper bounds: Derivative-free optimization is also bounded for convex Lipschitz objectives using zeroth-order oracle queries and established stochastic optimization algorithms.This provides the comparison case using objective-function measurements rather than first-order queries.
  • 4.3 When is SMD superior to SGD?: ∥⃗Γ∥2 2 can be up to a factor of p smaller than ∥⃗Γ∥2 1, so SMD may scale quadratically better in parameter dimension when Γj values are comparable.For Γ1≈···≈Γp, the SGD bound is quadratically worse in p under the stated comparison.
  • 4.3 When is SMD superior to SGD?: In the toy model, λ2=Θ(1), λ1=Θ(1/n), ∥⃗Γ∥2 1=Θ(n2), and ∥⃗Γ∥2 2=Θ(n), making SGD and SMD asymptotically equivalent up to logarithmic factors and constants.The comparison depends on both strong-convexity parameters and gradient-estimator norms.
  • 4.3 When is SMD superior to SGD?: The paper does not establish whether Euclidean SGD or l1-based SMD generally gives better practical upper bounds for variational algorithms.The conclusion leaves the usual geometry choice as an open question.

5 Oracle separation between zeroth-order and first-order optimization strategies for variational algorithms

The paper separates zeroth-order from first-order oracle strategies for a family of variational optimization problems, showing that analytic gradient queries can substantially improve convergence and that higher-order access cannot beat the resulting scaling beyond constants.

  • 5 Oracle separation between zeroth-order and first-order optimization strategies for variational algorithms: Zeroth-order, 100ε-vicinity algorithms require a lower-bounded number of queries to optimize H^ε_n to precision ε.The lower bound applies to strategies restricted to objective-function measurements near the optimum.
  • 5 Oracle separation between zeroth-order and first-order optimization strategies for variational algorithms: First-order queries admit substantially faster optimization of H^ε_n than zeroth-order queries, using a simple stochastic gradient descent algorithm.The comparison is established through matching upper and lower bounds for the constructed problem family.
  • 5 Oracle separation between zeroth-order and first-order optimization strategies for variational algorithms: A first-order algorithm based on stochastic gradient descent achieves error at most ε for H^ε_n.The theorem identifies stochastic gradient descent as the constructive strategy attaining the first-order upper bound.
  • 5 Oracle separation between zeroth-order and first-order optimization strategies for variational algorithms: The lower-bound framework extends to arbitrary kth-order oracle queries, with the stated general lower bound applying without restricting the queried state domain.This establishes a broader benchmark for black-box optimization strategies beyond the zeroth- and first-order cases.

5.1 Defining Hǫn

The constructed family H^ε_n consists of perturbed 1-local Hamiltonians whose perturbation strength is controlled by a bias parameter and whose direction is encoded by a binary vector.

  • 5.1 Defining H^ε_n: H^ε_n is defined from observables perturbed around a simple 1-local Hamiltonian.The family is parameterized through a precision-dependent bias parameter.
  • 5.1 Defining H^ε_n: The binary vector v ∈ {−1,1}^n encodes the perturbation direction, while δ controls its strength.For fixed δ, the family contains 2^n observables indexed by v.
  • 5.1 Defining H^ε_n: The unperturbed Hamiltonian H_0 has ground state |π/4⟩^⊗n, and the perturbed observables have minimum eigenvalue −n.The single-qubit state |π/4⟩ is defined explicitly in the construction.

5.2 Proof of Theorem 5.1: zeroth-order lower bound for Hǫ

The zeroth-order lower bound reduces optimization to identifying a hidden perturbation vector, then uses separation and information-theoretic arguments to show that many objective-only queries are necessary.

  • 5.2 Proof of Theorem 5.1: zeroth-order lower bound for H^ε_n: The proof restricts to a packed subset M^ε_n whose separated observables encode a hidden parameter in the n-dimensional hypercube.Optimizing this subset is sufficient to lower-bound optimization of the full family.
  • 5.2 Proof of Theorem 5.1: zeroth-order lower bound for H^ε_n: Any sufficiently accurate optimizer for the selected family can identify the hidden vector v with probability at least 2/3.The reduction uses the fact that near-optimal states for distinct observables are separated.
  • 5.2 Proof of Theorem 5.1: zeroth-order lower bound for H^ε_n: The packing separation is quantified through d(v,v′), which scales with Hamming distance and the perturbation strength.The construction ensures distinct vectors are separated by at least n/4 in Hamming distance.
  • 5.2 Proof of Theorem 5.1: zeroth-order lower bound for H^ε_n: Zeroth-order oracle transcripts reveal only limited mutual information about the hidden vector, yielding the query lower bound.After T queries, the mutual information is upper bounded by O(Tδ^4), and Fano’s inequality converts this into an identification lower bound.
  • 5.2 Proof of Theorem 5.1: zeroth-order lower bound for H^ε_n: The resulting lower bound transfers from hidden-vector identification to optimizing H^ε_n to expected error at most ε.The reduction completes the proof of Theorem 5.1.

5.3 Proof of Theorem 5.2: upper bound for optimizing Hǫn

For a natural product-state parameterization, the induced objective is strongly convex in a feasible neighborhood, enabling projected stochastic gradient descent to optimize H^ε_n with the stated first-order query bound.

  • 5.3 Proof of Theorem 5.2: upper bound for optimizing H^ε_n: The parameterization uses an n-parameter product-state ansatz whose ground states lie inside the feasible set B_∞(δ).States associated with B_∞(δ) are contained in the 100ε-optimum region.
  • 5.3 Proof of Theorem 5.2: upper bound for optimizing H^ε_n: The induced objective is 0.1-strongly convex on B_∞(δ) with respect to the Euclidean norm.The Hessian diagonal entries are bounded below using δ < 0.7.
  • 5.3 Proof of Theorem 5.2: upper bound for optimizing H^ε_n: Projected stochastic gradient descent outputs a parameter whose expected objective error is at most ε for every H ∈ H^ε_n.The projection keeps the iterates within the feasible neighborhood used for the convexity argument.
  • 5.3 Proof of Theorem 5.2: upper bound for optimizing H^ε_n: The first-order strategy requires O(n^2/ε) queries when the strong convexity parameter is Θ(1).The bound follows from the stochastic optimization rate used in the analysis.
  • 5.3 Proof of Theorem 5.2: upper bound for optimizing H^ε_n: Unprojected stochastic gradient descent is noted as likely effective for this family because all local optima are global minima.This observation is presented as a sidenote rather than the proved projected algorithmic guarantee.

5.4 Proof of Theorem 5.3: general query lower bound for optimizing Hǫn

The proof establishes a general lower bound for optimizing H^ε_n through information limits on arbitrary-order oracle queries. A matching first-order SGD upper bound shows that SGD is essentially optimal for this family.

  • 6 Conclusion and open questions: The lower bound permits arbitrary query orders and states outside the 100ε-optimum, while proving the easier task of optimizing M^ε_n ⊂ H^ε_n.This broadens the lower-bound setting beyond the restrictions used for the earlier theorem.
  • 6 Conclusion and open questions: The oracle’s output reveals no more information about the hidden parameter than its internal coin flip, by the data processing inequality.The hidden parameter, coin-flip outcome, and oracle output form a Markov chain.
  • 6 Conclusion and open questions: The information accumulated over T oracle queries is bounded by T times the maximum single-query mutual information.The proof bounds the per-query information using conditional distributions and relative entropy.
  • 6 Conclusion and open questions: At least Ω oracle queries are required to optimize H^ε_n with worst-case expected error at most ε.The lower bound follows after showing that identifying the hidden bias parameter requires at least Ω oracle queries.
  • 6 Conclusion and open questions: SGD matches the lower bound up to constant factors, making it essentially optimal among black-box strategies for optimizing H^ε_n.The matching upper bound uses first-order oracle queries and stochastic gradient descent.

6 Conclusion and open questions

The paper introduces a practical black-box model, proves a zeroth- versus first-order query-cost separation for simple observables, and derives convex-region bounds for SGD and SMD. It identifies strong convexity, geometry, higher-order measurements, and noise as important directions for future work.

  • 6 Conclusion and open questions: The black-box analysis gives rigorous convex-region query bounds for SGD and stochastic mirror descent, with the stronger method depending on parameter settings.For the toy problem, SGD outperforms SMD by only a logarithmic factor in the number of parameters.
  • 6 Conclusion and open questions: Analytic gradient measurements with stochastic first-order optimization can outperform every zeroth-order strategy for the analyzed observable family.The separation compares objective-function measurements with direct gradient measurements near the optimum.
  • 6 Conclusion and open questions: For H^ε_n, an appropriate ansatz makes the objective Θ(1)-strongly convex in the 2-norm, yielding an O(1/ε) SGD query bound.The paper contrasts this with typical O(1/ε^2) scaling without a strong-convexity guarantee.
  • 6 Conclusion and open questions: The analyzed H^ε_n observables are extremely simple, being 1-local with unentangled ground states, limiting conclusions about higher-order measurements.Higher-order measurements showed no benefit for this toy family, but may behave differently on more complicated problems.
  • 6 Conclusion and open questions: The paper leaves analytic gradient measurements under noise unresolved, especially because biased noise is less understood than unbiased noise.The authors specifically identify convergence-rate effects in noisy settings as an open question.

A Background on stochastic gradient and mirror descent

This section introduces stochastic gradient and mirror descent as background for convex optimization analysis.

  • A Background on stochastic gradient and mirror descent: The section reviews preliminaries on convex optimization and stochastic descent algorithms, following an existing review.These preliminaries support the later analysis of stochastic optimization methods.

A.1 Gradient descent

Projected gradient descent iteratively moves along a gradient-based decrease direction while remaining feasible, and stochastic unbiased gradient estimates preserve the qualitative convergence picture. Strong convexity supplies sharper guarantees than ordinary convexity.

  • A.1 Gradient descent: Projected gradient descent takes a gradient step and projects the result back into the feasible set X.The projection is Euclidean, and the update can also be viewed as a regularized linearization of f.
  • A.1 Gradient descent: Strong convexity requires the objective to dominate its first-order approximation by a norm-dependent quadratic term.The definition applies for every pair of feasible points and any chosen norm.
  • A.1 Gradient descent: For λ-strongly convex Lipschitz objectives, projected gradient descent achieves an iteration bound logarithmic in 1/ε.Strong convexity is characterized through the Hessian eigenvalues in the twice-differentiable case.
  • A.1 Gradient descent: Using noisy unbiased gradient estimates yields stochastic gradient descent with qualitatively unchanged convergence results.The stochastic gradient oracle returns an estimate whose expectation equals the true gradient.

A.2 Mirror descent

Mirror descent extends gradient-based optimization to non-Euclidean geometries, enabling convergence analyses that match the geometry and gradient norms of the problem. The section develops deterministic and stochastic mirror-descent procedures and states convergence guarantees for convex and strongly convex objectives.

  • Motivation: Mirror descent can avoid the dimension dependence of Euclidean gradient descent when gradients are naturally bounded in the dual norm of an l1 geometry.If all partial derivatives are bounded by 1, the Euclidean Lipschitz bound can scale with the dimension, whereas the relevant l∞ bound is dimension-independent.
  • Mirror descent framework: A mirror map generates the problem geometry through a Bregman divergence, with squared Euclidean distance and generalized KL divergence as examples.The mirror map also supports a dual-space interpretation of the update and projection back onto the feasible set.
  • Mirror descent framework: Mirror descent performs a gradient step in dual space, maps back to the original space, and projects onto the feasible set using the generated Bregman divergence.This construction generalizes ordinary gradient descent beyond Euclidean spaces.
  • Convergence guarantees: The section states convergence bounds for mirror descent when the objective is convex and Lipschitz, including Euclidean and l1-geometry settings.The l1 setup assumes a bounded feasible region and uses an appropriate mirror map and stepsizes.
  • Stochastic mirror descent: Stochastic mirror descent replaces exact gradients with unbiased stochastic estimates and has corresponding guarantees for convex and strongly convex objectives.The stochastic oracle is assumed to have bounded expected squared l∞ norm, and strong convexity permits acceleration.
Loading 1901.05374v1…