Iteration Complexity of Variational Quantum Algorithms

Vyacheslav Kungurtsev; Georgios Korpas; Jakub Marecek; Elton Yechao Zhu

doi:10.22331/q-2024-10-10-1495

Iteration Complexity of Variational Quantum Algorithms

Vyacheslav Kungurtsev¹, Georgios Korpas^1,2, Jakub Marecek¹, and Elton Yechao Zhu³

¹Department of Computer Science, Czech Technical University in Prague, Karlovo nam. 13, Prague 2, Czech Republic
²Archimedes Research Unit on AI, Data Science and Algorithms, Athena Research and Innovation Center, 15125 Marousi, Greece
³Fidelity Center for Applied Technology, FMR LLC, Boston, MA 02210, USA

Published:	2024-10-10, volume 8, page 1495
Eprint:	arXiv:2209.10615v4
Doi:	https://doi.org/10.22331/q-2024-10-10-1495
Citation:	Quantum 8, 1495 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Popular summary

Variational quantum algorithms (VQA) are among the most popular near-term applications of quantum computers. There, a parametrized quantum circuit encodes an objective function, and a classical algorithm adjusts parameters in the parametrized quantum circuit. The question is how many times this pairs of steps needs to be repeated to achieve a small gradient in expectation.

We answer this question in several settings, including SPSA and the parameter shift rule, assuming that there are both Gaussian and biased noises. The biased-noise assumption may be of independent interest for both analyses of quantum algorithms and for analyses of classical algorithms with biased noise.

► BibTeX data

@article{Kungurtsev2024iterationcomplexity,
  doi = {10.22331/q-2024-10-10-1495},
  url = {https://doi.org/10.22331/q-2024-10-10-1495},
  title = {Iteration {C}omplexity of {V}ariational {Q}uantum {A}lgorithms},
  author = {Kungurtsev, Vyacheslav and Korpas, Georgios and Marecek, Jakub and Zhu, Elton Yechao},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1495},
  month = oct,
  year = {2024}
}

► References

[1] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alá n Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18, 023023 (2016).
https://doi.org/10.1088/1367-2630/18/2/023023

[2] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C Benjamin. ``Theory of variational quantum simulation''. Quantum 3, 191 (2019).
https://doi.org/10.22331/q-2019-10-07-191

[3] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. ``Variational quantum algorithms''. Nature Reviews Physics 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9

[4] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O'Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Victor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal. ``Quantum Optimization: Potential, Challenges, and the Path Forward'' (2023). arXiv:2312.02279.
arXiv:2312.02279

[5] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. ``Warm-starting quantum optimization''. Quantum 5, 479 (2021).
https://doi.org/10.22331/q-2021-06-17-479

[6] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. ``Quantum algorithms for quantum chemistry and quantum materials science''. Chemical Reviews 120, 12685–12717 (2020).
https://doi.org/10.1021/acs.chemrev.9b00829

[7] Lin Lin and Yu Tong. ``Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers''. PRX Quantum 3, 010318 (2022).
https://doi.org/10.1103/PRXQuantum.3.010318

[8] Travis S Humble, Andrea Delgado, Raphael Pooser, Christopher Seck, Ryan Bennink, Vicente Leyton-Ortega, C-C Joseph Wang, Eugene Dumitrescu, Titus Morris, Kathleen Hamilton, et al. ``Snowmass white paper: Quantum computing systems and software for high-energy physics research'' (2022).
arXiv:2203.07091

[9] Andrew Blance and Michael Spannowsky. ``Quantum machine learning for particle physics using a variational quantum classifier''. Journal of High Energy Physics 2021, 1–20 (2021).
https://doi.org/10.1007/JHEP02(2021)212

[10] Aram W. Harrow and John C. Napp. ``Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms''. Physical Review Letters 126, 140502 (2021).
https://doi.org/10.1103/PhysRevLett.126.140502

[11] Artur K Ekert, Carolina Moura Alves, Daniel KL Oi, Michał Horodecki, Paweł Horodecki, and Leong Chuan Kwek. ``Direct estimations of linear and nonlinear functionals of a quantum state''. Physical Review Letters 88, 217901 (2002).
https://doi.org/10.1103/PhysRevLett.88.217901

[12] Laurin E Fischer, Daniel Miller, Francesco Tacchino, Panagiotis Kl Barkoutsos, Daniel J Egger, and Ivano Tavernelli. ``Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space''. Physical Review Research 4, 033027 (2022).
https://doi.org/10.1103/PhysRevResearch.4.033027

[13] James C Spall et al. ``Multivariate stochastic approximation using a simultaneous perturbation gradient approximation''. IEEE transactions on automatic control 37, 332–341 (1992).
https://doi.org/10.1103/10.1109/9.119632

[14] Xavier Bonet-Monroig, Hao Wang, Diederick Vermetten, Bruno Senjean, Charles Moussa, Thomas Bäck, Vedran Dunjko, and Thomas E O'Brien. ``Performance comparison of optimization methods on variational quantum algorithms''. Physical Review A 107, 032407 (2023).
https://doi.org/10.1103/PhysRevA.107.032407

[15] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. ``Quantum circuit learning''. Physical Review A 98 (2018).
https://doi.org/10.1103/physreva.98.032309

[16] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. ``Evaluating analytic gradients on quantum hardware''. Physical Review A 99, 032331 (2019).
https://doi.org/10.1103/PhysRevA.99.032331

[17] Leonardo Banchi and Gavin E. Crooks. ``Measuring analytic gradients of general quantum evolution with the stochastic parameter shift rule''. Quantum 5, 386 (2021).
https://doi.org/10.22331/q-2021-01-25-386

[18] Giuliano Benenti, Giulio Casati, Davide Rossini, and Giuliano Strini. ``Principles of quantum computation and information: a comprehensive textbook''. World Scientific. (2019).
https://doi.org/10.1142/10909

[19] Vivek S Borkar. ``Stochastic approximation: a dynamical systems viewpoint''. Volume 48. Springer. (2009).
https://doi.org/10.1007/978-93-86279-38-5

[20] A Doucet and V Tadic. ``Asymptotic bias of stochastic gradient search''. Annals of Applied Probability 27, 3255–3304 (2017).
https://doi.org/10.1214/16-AAP1272

[21] Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. ``Non-asymptotic analysis of biased stochastic approximation scheme''. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory. Volume 99 of Proceedings of Machine Learning Research, pages 1944–1974. PMLR (2019). url: https://proceedings.mlr.press/v99/karimi19a.html.
https://proceedings.mlr.press/v99/karimi19a.html

[22] Ahmad Ajalloeian and Sebastian U. Stich. ``Analysis of SGD with biased gradient estimators'' (2020). arXiv:2008.00051.
arXiv:2008.00051

[23] Ruobing Chen. ``Stochastic derivative-free optimization of noisy functions''. PhD thesis. Lehigh University. (2015). url: https://preserve.lehigh.edu/lehigh-scholarship/graduate-publications-theses-dissertations/theses-dissertations/stochastic-7.
https://preserve.lehigh.edu/lehigh-scholarship/graduate-publications-theses-dissertations/theses-dissertations/stochastic-7

[24] Oleg Granichin and Natalia Amelina. ``Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances''. IEEE Transactions on Automatic Control 60, 1653–1658 (2014).
https://doi.org/10.1109/TAC.2020.3024169

[25] Andrei Boiarov, Oleg Granichin, and Hou Wenguang. ``Simultaneous perturbation stochastic approximation for clustering of a gaussian mixture model under unknown but bounded disturbances''. In 2017 IEEE Conference on Control Technology and Applications (CCTA). Pages 1740–1745. IEEE (2017).
https://doi.org/10.1109/CCTA.2017.8062708

[26] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5 (2014).
https://doi.org/10.1038/ncomms5213

[27] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[28] Dave Wecker, Matthew B. Hastings, and Matthias Troyer. ``Progress towards practical quantum variational algorithms''. Physical Review A 92 (2015).
https://doi.org/10.1103/physreva.92.042303

[29] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[30] Oleksandr Kyriienko, Annie E. Paine, and Vincent E. Elfving. ``Solving nonlinear differential equations with differentiable quantum circuits''. Physical Review A 103, 052416 (2021).
https://doi.org/10.1103/PhysRevA.103.052416

[31] Razin A. Shaikh, Sara Sabrina Zemljic, Sean Tull, and Stephen Clark. ``The Conceptual VAE'' (2022). arXiv:2203.11216.
arXiv:2203.11216

[32] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor Rieffel, Davide Venturelli, and Rupak Biswas. ``From the quantum approximate optimization algorithm to a quantum alternating operator ansatz''. Algorithms 12, 34 (2019).
https://doi.org/10.3390/a12020034

[33] Guillaume Verdon, Jacob Marks, Sasha Nanda, Stefan Leichenauer, and Jack Hidary. ``Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm'' (2019). arXiv:1910.02071.
arXiv:1910.02071

[34] Benjamin Nachman, Miroslav Urbanek, Wibe A. de Jong, and Christian W. Bauer. ``Unfolding quantum computer readout noise''. npj Quantum Information 6 (2020).
https://doi.org/10.1038/s41534-020-00309-7

[35] Gavin E. Crooks. ``Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition'' (2019). arXiv:1905.13311.
arXiv:1905.13311

[36] Jun Li, Xiaodong Yang, Xinhua Peng, and Chang-Pu Sun. ``Hybrid quantum-classical approach to quantum optimal control''. Physical Review Letters 118 (2017).
https://doi.org/10.1103/physrevlett.118.150503

[37] Andrea Mari, Thomas R. Bromley, and Nathan Killoran. ``Estimating the gradient and higher-order derivatives on quantum hardware''. Physical Review A 103 (2021).
https://doi.org/10.1103/physreva.103.012405

[38] C. C. Y. Dorea. ``Expected number of steps of a random optimization method''. Journal of Optimization Theory and Applications 39, 165–171 (1983).
https://doi.org/10.1007/bf00934526

[39] R. Wengert. ``A simple automatic derivative evaluation program''. Communications of the ACM 7, 463–464 (1964).
https://doi.org/10.1145/355586.364791

[40] Yurii Nesterov. ``Smooth minimization of non-smooth functions''. Mathematical programming 103, 127–152 (2005).
https://doi.org/10.1007/s10107-004-0552-5

[41] John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. ``Optimal rates for zero-order convex optimization: The power of two function evaluations''. IEEE Transactions on Information Theory 61, 2788–2806 (2015).
https://doi.org/10.1109/TIT.2015.2409256

[42] Yurii Nesterov and Vladimir Spokoiny. ``Random gradient-free minimization of convex functions''. Foundations of Computational Mathematics 17, 527–566 (2015).
https://doi.org/10.1007/s10208-015-9296-2

[43] Navin Khaneja, Timo Reiss, Cindie Kehlet, Thomas Schulte-Herbrüggen, and Steffen J. Glaser. ``Optimal control of coupled spin dynamics: design of NMR pulse sequences by gradient ascent algorithms''. Journal of Magnetic Resonance 172, 296–305 (2005).
https://doi.org/10.1016/j.jmr.2004.11.004

[44] Javier Gil Vidal and Dirk Oliver Theis. ``Calculus on parameterized quantum circuits'' (2018). arXiv:1812.06323.
arXiv:1812.06323

[45] Artur F Izmaylov, Robert A Lang, and Tzu-Ching Yen. ``Analytic gradients in variational quantum algorithms: Algebraic extensions of the parameter-shift rule to general unitary transformations''. Physical Review A 104, 062443 (2021).
https://doi.org/10.1103/PhysRevA.104.062443

[46] David Wierichs, Josh Izaac, Cody Wang, and Cedric Yen-Yu Lin. ``General parameter-shift rules for quantum gradients''. Quantum 6, 677 (2022).
https://doi.org/10.22331/q-2022-03-30-677

[47] Dirk Oliver Theis. ``Optimality of finite-support parameter shift rules for derivatives of variational quantum circuits'' (2021).

[48] Jakob S. Kottmann, Abhinav Anand, and Alán Aspuru-Guzik. ``A feasible approach for automatically differentiable unitary coupled-cluster on quantum computers''. Chemical Science 12, 3497–3508 (2021).
https://doi.org/10.1039/d0sc06627c

[49] Bálint Koczor and Simon C Benjamin. ``Quantum analytic descent''. Physical Review Research 4, 023017 (2022).
https://doi.org/10.1103/PhysRevResearch.4.023017

[50] Andrew R Conn, Katya Scheinberg, and Luis N Vicente. ``Introduction to derivative-free optimization''. SIAM. (2009).
https://doi.org/10.1137/1.9780898718768

[51] Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. ``A theoretical and empirical comparison of gradient approximations in derivative-free optimization''. Foundations of Computational Mathematics 22, 507–560 (2022).
https://doi.org/10.1007/s10208-021-09513-z

[52] Daniel C Chin. ``Comparative study of stochastic algorithms for system optimization based on gradient approximations''. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 27, 244–249 (1997).
https://doi.org/10.1109/3477.558808

[53] Saeed Ghadimi and Guanghui Lan. ``Stochastic first-and zeroth-order methods for nonconvex stochastic programming''. SIAM Journal on Optimization 23, 2341–2368 (2013).
https://doi.org/10.1137/120880811

[54] Krishnakumar Balasubramanian and Saeed Ghadimi. ``Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates''. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems. Volume 31. Curran Associates, Inc. (2018).
https://doi.org/10.48550/arXiv.1809.06474

[55] Md. Sajid Anis et al. ``Qiskit: An open-source framework for quantum computing'' (2021).

[56] Isaac L. Chuang Michael A. Nielsen. ``Quantum computation and quantum information''. Cambridge University Press. (2011). 10th anniversary edition edition.
https://doi.org/10.1017/CBO9780511976667

[57] Giuliano Gadioli La Guardia. ``Quantum error correction''. Springer International Publishing. (2020).
https://doi.org/10.1007/978-3-030-48551-1

[58] Swamit S Tannu and Moinuddin K Qureshi. ``Mitigating measurement errors in quantum computers by exploiting state-dependent bias''. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture. Pages 279–290. (2019).
https://doi.org/10.1145/3352460.3358265

[59] M. D. Shulman, O. E. Dial, S. P. Harvey, H. Bluhm, V. Umansky, and A. Yacoby. ``Demonstration of entanglement of electrostatically coupled singlet-triplet qubits''. Science 336, 202–205 (2012).
https://doi.org/10.1126/science.1217692

[60] T. F. Watson, S. G. J. Philips, E. Kawakami, D. R. Ward, P. Scarlino, M. Veldhorst, D. E. Savage, M. G. Lagally, Mark Friesen, S. N. Coppersmith, M. A. Eriksson, and L. M. K. Vandersypen. ``A programmable two-qubit quantum processor in silicon''. Nature 555, 633–637 (2018).
https://doi.org/10.1038/nature25766

[61] Ioan M. Pop, Kurtis Geerlings, Gianluigi Catelani, Robert J. Schoelkopf, Leonid I. Glazman, and Michel H. Devoret. ``Coherent suppression of electromagnetic dissipation due to superconducting quasiparticles''. Nature 508, 369–372 (2014).
https://doi.org/10.1038/nature13017

Cited by

[1] Daniel Mastropietro, Georgios Korpas, Vyacheslav Kungurtsev, and Jakub Marecek, "Parallel Variational Quantum Algorithms With Gradient-Informed Restart to Speed Up Optimization in the Presence of Barren Plateaus", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[2] James Hancock, Matthew Craven, Craig McNeile, and Davide Vadacchino, "Investigating Techniques to Optimise the Layout of Turbines in a Windfarm Using a Quantum Computer", Journal of Quantum Computing 7 1, 55 (2025).

[3] Farzaneh Shayeganfar, Ali Ramazani, Veera Sundararaghavan, and Yuhua Duan, "Quantum graph learning and algorithms applied in quantum computer sciences and image classification", Applied Physics Reviews 12 2, 021327 (2025).

[4] Adelina Bärligea, Benedikt Poggel, and Jeanette Miriam Lorenz, "Scalability challenges in variational quantum optimization under stochastic noise", Physical Review A 112 3, 032407 (2025).

[5] Juan C. Boschero, Ward van der Schoot, and Niels M. P. Neumann, "A Triple-Hybrid Quantum Support Vector Machine Using Classical, Quantum Gate-based and Quantum Annealing-based Computing", arXiv:2511.05237, (2025).

[6] Marco Wiedmann, Marc Hölle, Maniraman Periyasamy, Nico Meyer, Christian Ufrecht, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler, "An Empirical Comparison of Optimizers for Quantum Machine Learning with SPSA-based Gradients", arXiv:2305.00224, (2023).

[7] Cenk Tüysüz, Su Yeon Chang, Maria Demidik, Karl Jansen, Sofia Vallecorsa, and Michele Grossi, "Symmetry Breaking in Geometric Quantum Machine Learning in the Presence of Noise", PRX Quantum 5 3, 030314 (2024).

[8] Megan C. Giron, Georgios Korpas, Waqas Parvaiz, Prashant Malik, and Johannes Aspman, "Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing (May 2023)", IEEE Transactions on Quantum Engineering 4, TQE.2023 (2023).

[9] Andrea Ceschini, Francesco Mauro, Francesca De Falco, Alessandro Sebastianelli, Alessio Verdone, Antonello Rosato, Bertrand Le Saux, Massimo Panella, Paolo Gamba, and Silvia L. Ullo, "From Graphs to Qubits: A Critical Review of Quantum Graph Neural Networks", arXiv:2408.06524, (2024).

[10] Maniraman Periyasamy, Axel Plinge, Christopher Mutschler, Daniel D. Scherer, and Wolfgang Mauerer, "Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule", arXiv:2404.15751, (2024).

[11] James Hancock, Matthew J. Craven, Craig McNeile, and Davide Vadacchino, "Investigating Techniques to Optimise the Layout of Turbines in a Windfarm using a Quantum Computer", arXiv:2312.13123, (2023).

[12] Georgios Korpas, Vyacheslav Kungurtsev, and Jakub Mareček, "Undecidable problems associated with variational quantum algorithms", arXiv:2503.23723, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-10-19 17:24:15) and SAO/NASA ADS (last updated successfully 2026-10-19 17:24:16). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.