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

arXiv: https://arxiv.org/abs/1901.05374 · HTML: https://mlsanity.com/paper/1901.05374/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2019.

## Built on by (most cited first, 30 of 31)

- [QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer](https://mlsanity.com/paper/2102.12846/) (2021)
- [Equivalence of quantum barren plateaus to cost concentration and narrow gorges](https://mlsanity.com/paper/2104.05868/) (2021)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [Universal Adversarial Examples and Perturbations for Quantum Classifiers](https://mlsanity.com/paper/2102.07788/) (2021)
- [Quantum Multi-Agent Meta Reinforcement Learning](https://mlsanity.com/paper/2208.11510/) (2022)
- [The dilemma of quantum neural networks](https://mlsanity.com/paper/2106.04975/) (2021)
- [Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications](https://mlsanity.com/paper/2307.00908/) (2023)
- [Reduction of finite sampling noise in quantum neural networks](https://mlsanity.com/paper/2306.01639/) (2023)
- [Adaptive shot allocation for fast convergence in variational quantum algorithms](https://mlsanity.com/paper/2108.10434/) (2021)
- [Quantum Boltzmann machine learning of ground-state energies](https://mlsanity.com/paper/2410.12935/) (2024)
- [Dual-Parameterized Quantum Circuit GAN Model in High Energy Physics](https://mlsanity.com/paper/2103.15470/) (2021)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [Density Matrix Emulation of Quantum Recurrent Neural Networks for Multivariate Time Series Prediction](https://mlsanity.com/paper/2310.20671/) (2023)
- [LAWS: Look Around and Warm-Start Natural Gradient Descent for Quantum Neural Networks](https://mlsanity.com/paper/2205.02666/) (2022)
- [Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry](https://mlsanity.com/paper/2206.04663/) (2022)
- [Bayesian Learning of Parameterised Quantum Circuits](https://mlsanity.com/paper/2206.07559/) (2022)
- [Exponential Quantum Communication Advantage in Distributed Inference and Learning](https://mlsanity.com/paper/2310.07136/) (2023)
- [sQUlearn -- A Python Library for Quantum Machine Learning](https://mlsanity.com/paper/2311.08990/) (2023)
- [Modeling stochastic eye tracking data: A comparison of quantum generative adversarial networks and Markov models](https://mlsanity.com/paper/2408.00673/) (2024)
- [Quantum Speedup of Natural Gradient for Variational Bayes](https://mlsanity.com/paper/2106.05807/) (2021)
- [Image Compression and Classification Using Qubits and Quantum Deep Learning](https://mlsanity.com/paper/2110.05476/) (2021)
- [Mode connectivity in the loss landscape of parameterized quantum circuits](https://mlsanity.com/paper/2111.05311/) (2021)
- [An Introduction to Quantum Computing for Statisticians and Data Scientists](https://mlsanity.com/paper/2112.06587/) (2021)
- [Efficient Gradient Estimation for Parameterized Quantum Systems with Lie Algebraic Symmetries](https://mlsanity.com/paper/2404.05108/) (2024)
- [Quantum Natural Stochastic Pairwise Coordinate Descent](https://mlsanity.com/paper/2407.13858/) (2024)
- [Solving Conic Programs over Sparse Graphs using a Variational Quantum Approach: The Case of the AC Optimal Power Flow](https://mlsanity.com/paper/2509.00341/) (2025)
- [A Case For Noisy Shallow Gate-Based Circuits In Quantum Machine Learning](https://mlsanity.com/paper/2112.06712/) (2021)
- [Quantum Approximation of Normalized Schatten Norms and Applications to Learning](https://mlsanity.com/paper/2206.11506/) (2022)
- [Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE](https://mlsanity.com/paper/2311.08502/) (2023)
- [Benchmarking a wide range of optimisers for solving the Fermi-Hubbard model using the variational quantum eigensolver](https://mlsanity.com/paper/2411.13742/) (2024)

## Abstract (arXiv)

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.