# Iteration Complexity of Variational Quantum Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2022.

## Built on by (most cited first, 2 of 2)

- [An Empirical Comparison of Optimizers for Quantum Machine Learning with SPSA-based Gradients](https://mlsanity.com/paper/2305.00224/) (2023)
- [Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule](https://mlsanity.com/paper/2404.15751/) (2024)

## Abstract (arXiv)

There has been much recent interest in near-term applications of quantum computers, i.e., using quantum circuits that have short decoherence times due to hardware limitations. Variational quantum algorithms (VQA), wherein an optimization algorithm implemented on a classical computer evaluates a parametrized quantum circuit as an objective function, are a leading framework in this space. An enormous breadth of algorithms in this framework have been proposed for solving a range of problems in machine learning, forecasting, applied physics, and combinatorial optimization, among others. In this paper, we analyze the iteration complexity of VQA, that is, the number of steps that VQA requires until its iterates satisfy a surrogate measure of optimality. We argue that although VQA procedures incorporate algorithms that can, in the idealized case, be modeled as classic procedures in the optimization literature, the particular nature of noise in near-term devices invalidates the claim of applicability of off-the-shelf analyses of these algorithms. Specifically, noise makes the evaluations of the objective function via quantum circuits biased. Commonly used optimization procedures, such as SPSA and the parameter shift rule, can thus be seen as derivative-free optimization algorithms with biased function evaluations, for which there are currently no iteration complexity guarantees in the literature. We derive the missing guarantees and find that the rate of convergence is unaffected. However, the level of bias contributes unfavorably to both the constant therein, and the asymptotic distance to stationarity, i.e., the more bias, the farther one is guaranteed, at best, to reach a stationary point of the VQA objective.