Stochastic gradient descent for hybrid quantum-classical optimization

Ryan Sweke; Frederik Wilde; Johannes Meyer; Maria Schuld; Paul K. Faehrmann; Barthélémy Meynard-Piganeau; Jens Eisert

Source-linked AI summary

Stochastic gradient descent for hybrid quantum-classical optimization

Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K. Faehrmann, Barthélémy Meynard-Piganeau, Jens Eisert

arXiv:1910.01155v3Oct 2, 2019quant-phcs.LG

TL;DR

Hybrid quantum-classical gradient methods incur substantial measurement costs because expectation values cannot be evaluated exactly. This paper formalizes finite-shot estimation as stochastic gradient descent, extends it with term sampling to obtain doubly stochastic estimators, and proves convergence guarantees across several settings. Numerically, treating stochasticity as a tunable hyper-parameter achieves highly accurate or state-of-the-art results with fewer circuit executions and measurements, while higher variance creates an efficiency–accuracy trade-off.

Problem
Quantum gradient optimization requires costly finite-shot expectation-value estimates, while the resulting stochastic behavior and convergence properties need formal treatment across relevant hybrid settings.
Method
The paper constructs unbiased finite-shot gradient estimators and combines measurement sampling with sampling over linear-combination terms to define doubly stochastic optimizers.
Results
Across VQE, QAOA, and quantum-classifier settings, the methods receive convergence guarantees, while numerical benchmarks show accurate results with fewer circuit executions and measurements.
Takeaways & Limitations
Single-shot estimation is theoretically sufficient, and stochastic settings can be tuned through learning rates, measurement shots, and sampled terms to balance efficiency and accuracy.
Takeaways & Limitations
Generic nonlinear functions of expectation values do not straightforwardly admit unbiased estimators from unbiased expectation-value estimates, and the fully general case remains open.

Abstract

from arXiv · show

Within the context of hybrid quantum-classical optimization, gradient descent based optimizers typically require the evaluation of expectation values with respect to the outcome of parameterized quantum circuits. In this work, we explore the consequences of the prior observation that estimation of these quantities on quantum hardware results in a form of stochastic gradient descent optimization. We formalize this notion, which allows us to show that in many relevant cases, including VQE, QAOA and certain quantum classifiers, estimating expectation values with $k$ measurement outcomes results in optimization algorithms whose convergence properties can be rigorously well understood, for any value of $k$. In fact, even using single measurement outcomes for the estimation of expectation values is sufficient. Moreover, in many settings the required gradients can be expressed as linear combinations of expectation values -- originating, e.g., from a sum over local terms of a Hamiltonian, a parameter shift rule, or a sum over data-set instances -- and we show that in these cases $k$-shot expectation value estimation can be combined with sampling over terms of the linear combination, to obtain "doubly stochastic" gradient descent optimizers. For all algorithms we prove convergence guarantees, providing a framework for the derivation of rigorous optimization results in the context of near-term quantum devices. Additionally, we explore numerically these methods on benchmark VQE, QAOA and quantum-enhanced machine learning tasks and show that treating the stochastic settings as hyper-parameters allows for state-of-the-art results with significantly fewer circuit executions and measurements.

1 Introduction

Hybrid quantum-classical gradient optimization is measurement-limited, motivating stochastic methods that reduce circuit-execution overhead while retaining analyzable convergence. The paper develops and evaluates doubly stochastic approaches across VQE, QAOA, and quantum classifiers.

Motivation: Finite measurement estimates make exact gradient descent impractical and create substantial circuit-repetition overhead.Previous approaches therefore used many measurements to approximate expectation values accurately.
Motivation: Measurement-based gradient evaluation naturally implements stochastic gradient descent with unbiased estimators and potential convergence guarantees.This connects hybrid quantum-classical optimization to established SGD theory and practice.
Scope: The paper studies stochastic techniques theoretically and numerically in VQE, QAOA, and quantum-classifier settings.It also examines heuristic extensions beyond these concrete settings.
Contribution: Sampling terms in gradient linear combinations together with finite-shot estimation yields doubly stochastic gradient descent.The linear combinations arise from Hamiltonian terms, parameter-shift terms, and data-set sums.
Contribution: A single measurement sample can save O(DMKN) measurements per optimization step for a quantum classifier with D data points, M observables, and K parameter-shift terms.The paper presents this as an extreme stochastic-gradient setting with potentially large efficiency gains.
Results: Higher estimator variance can require more optimization steps and produce non-optimal final solutions, but adaptive hyper-parameters can retain efficiency while reaching highly accurate solutions.Learning rate, measurement shots, and sampled linear-combination terms can be adjusted during optimization.

2 Setting and Idea

The paper casts finite-shot gradient estimation as SGD by constructing unbiased estimators for expectation-value-based derivatives. When derivatives are linear combinations, additional term sampling produces doubly stochastic updates that reduce measurements per step at the cost of higher variance.

SGD framework: SGD replaces each exact partial derivative in the gradient update with a random estimator, with unbiasedness supporting convergence analysis.The update uses a learning rate and estimator sequence in place of the exact gradient.
Setting: Hybrid quantum-classical losses depend on expectation values of observables generated by parameterized circuits, so gradients must be estimated from quantum measurements.The paper focuses on direct first-order gradient evaluation rather than zeroth-order finite differences.
Parameter-shift gradients: A K-term parameter-shift rule expresses each partial derivative as a linear combination of K expectation values at shifted circuit parameters.The shifts are defined by parameter-dependent offsets along coordinate directions.
Finite-shot estimation: The n-sample mean estimator averages n measurement outcomes to estimate an observable expectation value, remaining unbiased while its variance decreases as n increases.Linearly combining these estimators yields an unbiased derivative estimator requiring nK measurements.
Finite-shot estimation: The resulting SGD algorithm remains valid at n = 1, so large-shot gradient methods are finite-shot instances of the same stochastic framework.Exact expectation values are unavailable on quantum devices, making stochastic treatment the natural formulation.
Doubly stochastic estimation: Doubly stochastic estimation additionally samples terms from a derivative linear combination and applies correction weights, reducing the extreme-case cost to n measurements per step instead of nK.Uniform or importance sampling can be used, with importance sampling potentially lowering variance in some settings.
Extensions and trade-offs: The same construction applies to Hamiltonian, parameter-shift, and data-set linear combinations, but nonlinear functions of expectation values require more careful estimators.The paper notes that unbiased estimates generally do not survive nonlinear transformation and leaves the fully generic case open.

3 Unbiased estimators for VQE

The VQE loss is a linear combination of local Hamiltonian expectation values, enabling unbiased stochastic gradient estimators through parameter-shift measurements and term sampling. These estimators trade measurement cost against variance and convergence behavior.

VQE defines its loss from a local Hamiltonian, whose expectation-value terms can be differentiated and combined into an unbiased loss-gradient estimator.
nKM measurements per parameter update construct the direct estimator by evaluating n samples across M Hamiltonian terms and K parameter-shift terms.
nK measurements per parameter update suffice when one local Hamiltonian term is sampled instead of summing all terms.
Sampling parameter-shift terms, Hamiltonian terms, or both produces more efficient singly or doubly stochastic unbiased estimators.
Sampling commuting local-term subsets can decrease estimator variance while conserving the number of circuit executions per update.

4 Unbiased estimators for QAOA

QAOA uses the same expectation-value loss form as VQE but has an ansatz in which multiple gates share variational parameters. This structure yields a double-sum parameter-shift rule and enables additional sampling over gates.

QAOA minimizes the expectation value of a problem Hamiltonian, using a circuit architecture designed as a discretized adiabatic evolution.
Unlike circuits with distinct parameters per gate, QAOA assigns the same variational parameter to multiple constituent gates.
Assuming the constituent gates satisfy parameter-shift rules, VQE unbiased estimators transfer to QAOA and can additionally sample gates sharing a parameter.
When multiple gates share a parameter, its parameter-shift derivative becomes a double sum over gates and shift terms.

5 Unbiased estimators for MSE Quantum classifiers

MSE quantum classifiers require special treatment because their gradients involve nonlinear functions of expectation values. Independent unbiased estimators and data-instance sampling yield doubly stochastic gradient estimators with reduced measurement requirements.

MSE classifier gradients involve nonlinear functions of expectation values rather than only linear combinations of expectation values.
Independent unbiased estimators for an expectation value and its derivative produce an unbiased single-instance MSE-gradient estimator under a parameter-shift rule.
(K+1)n measurements construct the single-instance estimator, while sampling parameter-shift terms can reduce this cost to 2n measurements.
M(K+1)n measurements construct the full data-set estimator for the MSE gradient.
Sampling a batch B of data instances yields a doubly stochastic unbiased estimator requiring |B|(K+1)n measurements per parameter update.

6 Extensions to Generic Loss Functions

The paper extends stochastic-gradient constructions beyond regularized and mean-squared-error losses, but generic nonlinear loss functions present an unbiased-estimation obstacle. Polynomial functions admit U-statistic estimators, while arbitrary losses may require biased heuristics.

Regularization: Regularization preserves unbiasedness by adding the exact regularizer gradient to an unbiased estimator of the unregularized gradient.The paper verifies this by taking expectations term by term.
Generic loss functions: For a nonlinear gradient function f, applying f to an unbiased expectation estimator is generally biased because f(E[X]) ≠ E[f(X)].This prevents straightforward construction of unbiased estimators for generic nonlinear losses.
Polynomial losses: Polynomial gradient functions permit unbiased estimators constructed from independent samples using U-statistics.The construction uses m ≥ k samples for a degree-k polynomial and yields the minimum-variance unbiased estimator for the associated kernel.
Heuristic extensions: Arbitrary non-polynomial losses can use single-shot observable estimates and sampled linear combinations as biased estimators for practical evaluation.The paper notes that convergence bounds may still be possible, but leaves the completely general unbiased case open.

7 Convergence Guarantees

The paper develops convergence guarantees for its stochastic optimizers in simplified settings and identifies estimator variance as a key quantitative factor. The guarantees rely on assumptions including the Polyak–Łojasiewicz inequality, Lipschitz gradients, and bounded estimator second moments.

Convergence theorem: Theorem 1 gives SGD convergence when the loss has a Lipschitz gradient, attains a global minimum, satisfies the Polyak–Łojasiewicz inequality, and uses unbiased gradient estimators.The theorem applies to the paper’s previously constructed algorithms once Lipschitz continuity of the gradient is established.
Variance: Estimator variance determines the quantitative convergence bounds and influences the distance between the global optimum and the resulting solution.Bounding E[||g(t)(θ)||2] requires controlling the estimator variance.
Scope: The convergence analysis is limited to simplified PL settings, so more sophisticated theorems are needed for quantitative claims about realistic highly non-convex models.The paper does not explicitly derive the required variance bounds for those realistic settings.
Lipschitz continuity: Expectation values of parameterized quantum circuits are Lipschitz continuous under the stated finite-dimensional circuit and Hermitian-generator assumptions.This result supports applying the convergence theorem to the considered quantum optimization algorithms.
Extensions: The framework extends convergence analysis to sums and products of parameterized expectation values, including structures arising from parameter-shift rules and MSE losses.Lipschitz continuity is preserved under the relevant sums and products when the component functions are bounded.

8 Numerical Experiments and Benchmarks

Benchmark experiments examine shot-based and doubly stochastic optimization across VQE, QAOA, and quantum-enhanced classification, emphasizing measurement cost, learning-rate choices, and Hamiltonian sampling. Across these settings, small-shot methods converge rapidly in measurement terms, while increasing shot numbers or adapting learning rates can improve final-solution quality.

VQE: VQE experiments compare n-shot SGD under fixed, decaying, and Adam-controlled learning rates, with optimization steps and measurement cost used as evaluation axes.Each configuration was repeated 8 times, reporting minimum, mean, and maximum outcomes.
VQE: Increasing n reduces gradient variance and improves final VQE accuracy, while learning-rate decay or Adam can also improve solutions at very small n.For standard SGD and SGD with decay, higher-quality solutions eventually require increasing n; a combined strategy can exploit both effects.
VQE: Single-shot VQE SGD converges much faster than large-n algorithms when measured by circuit measurements.Measurement cost MCn is defined per optimization step, with results normalized as multiples of MC1.
VQE: Hamiltonian sampling adds another stochastic layer to n-shot VQE SGD, using sampled local terms or commuting term sets to reduce measurement requirements.The reported extreme-case experiment samples a single local Hamiltonian term, whereas practical implementations can sample commuting sets simultaneously.

9 Discussion and Conclusion

The work formalizes finite-shot expectation-value estimation as stochastic gradient descent and extends this framework to doubly stochastic optimization. Convergence is guaranteed in simplified settings, while numerical results show faster measurement-efficient optimization and motivate further noise-aware analysis.

Conclusions: Finite-shot expectation-value estimation makes exact gradient descent impossible and places practical hybrid optimizers within a stochastic-gradient-descent framework.The framework applies to VQE, QAOA, and MSE classification, including estimators using n = 1 measurement outcome.
Conclusions: Sampling terms in unbiased linear combinations yields doubly stochastic optimizers for Hamiltonian sums, parameter-shift expressions, and dataset-instance sums.This extends shot-based stochastic optimization by adding sampling over the terms contributing to the gradient or loss.
Numerical implications: Gradient-estimator variance controls solution accuracy, so small-shot and term-sampling methods may produce less fine-tuned solutions than large-shot algorithms.The discussion explicitly links estimator variance to the accuracy of converged solutions.
Numerical implications: Adaptive learning-rate heuristics can improve high-variance estimators, while small-shot and sampled-term methods can converge orders of magnitude faster in total measurements on benchmark tasks.The reported speed advantage concerns total measurements, even though the resulting solutions may be less fine-tuned.
Open directions: Realistic noise effects were omitted, and convergence guarantees for realistic non-convex landscapes remain open questions.The paper identifies noise-aware analysis and broader convergence theory as directions for future work.

A Proof of Theorem 2

The appendix proves Theorem 2 by establishing Lipschitz continuity for multivariate functions from coordinate-wise continuity and continuous partial derivatives. A telescoping decomposition and triangle inequality provide the core bound.

Lipschitz lemmas: Lemma 3 establishes Lipschitz continuity on closed intervals for continuously differentiable univariate functions, with constant L = supx∈[a,b] |f′(x)|.The result follows from the mean value theorem.
Coordinate-wise continuity: Definition 4 defines coordinate-wise Lipschitz continuity by fixing all other arguments and requiring the resulting univariate function gj,y to be Lipschitz.The induced function is gj,y(x) := f(y1, . . . , yj−1, x, yj, . . . yM−1).
Proof strategy: A multivariate difference f(x) − f(y) is decomposed into successive single-coordinate changes and bounded using the triangle inequality.This reduces the multivariate bound to coordinate-wise differences.
Theorem 2: Theorem 2 follows because all partial derivatives are continuous on R^M, allowing Lemma 5 to supply the required Lipschitz continuity.The appendix explicitly invokes Lemma 5 to complete the theorem proof.

B Parameterized circuit and optimization details

The VQE and MSE classifier experiments use the same parameterized quantum circuit, built from Pauli-rotation layers interleaved with CNOT ladders. The circuit contains 400 free parameters.

Parameterized circuit: The circuit used for both VQE and MSE classifier experiments consists of Pauli rotations interleaved with CNOT ladders.The figure caption denotes each single-qubit gate as σθ = e−iθσ for σ ∈ [X, Y, Z].
Parameterized circuit: 400 free parameters define the shared experimental circuit.This parameter count is stated for the circuit used in both experiment types.

C CO2 Emission Table

The paper reports estimated carbon emissions for numerical simulations and collaboration-related air travel. Transport dominates the reported total.

Numerical simulations: Numerical simulations consumed an estimated 85.1 kWh and produced 47.6 kg of CO2.The estimate uses 14,300 kernel hours, 5.75 W thermal design power per kernel, and 0.56 kg/kWh average German emissions.
Transport and total: Transport produced 4,804 kg of CO2, bringing the reported total to 4,847.5 kg.Both numerical-simulation and transport emissions were reported as offset.