Random Natural Gradient

Ioannis Kolotouros; Petros Wallden

doi:10.22331/q-2024-10-22-1503

Random Natural Gradient

Ioannis Kolotouros and Petros Wallden

University of Edinburgh, School of Informatics, EH8 9AB Edinburgh, United Kingdom

Published:	2024-10-22, volume 8, page 1503
Eprint:	arXiv:2311.04135v3
Doi:	https://doi.org/10.22331/q-2024-10-22-1503
Citation:	Quantum 8, 1503 (2024).

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

Abstract

Hybrid quantum-classical algorithms appear to be the most promising approach for near-term quantum applications. An important bottleneck is the classical optimization loop, where the multiple local minima and the emergence of barren plateaux make these approaches less appealing. To improve the optimization the Quantum Natural Gradient (QNG) method [15] was introduced – a method that uses information about the local geometry of the quantum state-space. While the QNG-based optimization is promising, in each step it requires more quantum resources, since to compute the QNG one requires $O(m^2)$ quantum state preparations, where $m$ is the number of parameters in the parameterized circuit. In this work we propose two methods that reduce the resources/state preparations required for QNG, while keeping the advantages and performance of the QNG-based optimization. Specifically, we first introduce the Random Natural Gradient (RNG) that uses random measurements and the classical Fisher information matrix (as opposed to the quantum Fisher information used in QNG). The essential quantum resources reduce to linear $O(m)$ and thus offer a quadratic "speed-up", while in our numerical simulations it matches QNG in terms of accuracy. We give some theoretical arguments for RNG and then benchmark the method with the QNG on both classical and quantum problems. Secondly, inspired by stochastic-coordinate methods, we propose a novel approximation to the QNG which we call Stochastic-Coordinate Quantum Natural Gradient that optimizes only a small (randomly sampled) fraction of the total parameters at each iteration. This method also performs equally well in our benchmarks, while it uses fewer resources than the QNG.

Popular summary

Variational quantum algorithms (VQAs) are algorithms that use both classical and quantum resources in a way that minimizes the technological requirements for the quantum part, making them a promising approach to deliver quantum advantage in the near-term era – the era before the development of fully scalable fault-tolerant quantum computing devices. Their versatility allows them to be used for many different problems, ranging from quantum chemistry and linear algebra to finance and optimization, to name a few. However, their actual usefulness is to be tested, as certain subsequent parts of these algorithms must be optimized in order to be comparable and competitive to their optimal classical counterparts. In this paper, we aim to improve a part of the classical-quantum loop, namely the optimization part of VQAs. Specifically, we use geometric information of the space of all possible parameterized quantum states considered, using random measurements. With our method, we achieve better optimization without the need for extra resources, significantly reducing the quantum resources and computation time from prior state-of-the-art.

► BibTeX data

@article{Kolotouros2024randomnatural,
  doi = {10.22331/q-2024-10-22-1503},
  url = {https://doi.org/10.22331/q-2024-10-22-1503},
  title = {Random {N}atural {G}radient},
  author = {Kolotouros, Ioannis and Wallden, Petros},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1503},
  month = oct,
  year = {2024}
}

► References

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

[2] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. ``Noisy intermediate-scale quantum algorithms''. Rev. Mod. Phys. 94, 015004 (2022).
https://doi.org/10.1103/RevModPhys.94.015004

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

[4] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets''. Nature 549, 242–246 (2017).
https://doi.org/10.1038/nature23879

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

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

[7] 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

[8] Abhinav Anand, Matthias Degroote, and Alán Aspuru-Guzik. ``Natural evolutionary strategies for variational quantum computation''. Machine Learning: Science and Technology 2, 045012 (2021).
https://doi.org/10.1088/2632-2153/abf3ac

[9] Tianchen Zhao, Giuseppe Carleo, James Stokes, and Shravan Veerapaneni. ``Natural evolution strategies and variational monte carlo''. Machine Learning: Science and Technology 2, 02LT01 (2020).
https://doi.org/10.1088/2632-2153/abcb50

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

[11] Amira Abbas, Robbie King, Hsin-Yuan Huang, William J. Huggins, Ramis Movassagh, Dar Gilboa, and Jarrod R. McClean. ``On quantum backpropagation, information reuse, and cheating measurement collapse'' (2023). arXiv:2305.13362.
arXiv:2305.13362

[12] Joseph Bowles, David Wierichs, and Chae-Yeun Park. ``Backpropagation scaling in parameterised quantum circuits'' (2024). arXiv:2306.14962.
arXiv:2306.14962

[13] Xuchen You and Xiaodi Wu. ``Exponentially many local minima in quantum neural networks''. In International Conference on Machine Learning. Pages 12144–12155. PMLR (2021). url: https://arxiv.org/abs/2110.02479.
arXiv:2110.02479

[14] Eric R. Anschuetz. ``Critical points in quantum generative models'' (2023). arXiv:2109.06957.
arXiv:2109.06957

[15] James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo. ``Quantum natural gradient''. Quantum 4, 269 (2020).
https://doi.org/10.22331/q-2020-05-25-269

[16] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan. ``Variational ansatz-based quantum simulation of imaginary time evolution''. npj Quantum Information 5 (2019).
https://doi.org/10.1038/s41534-019-0187-2

[17] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner, and Giuseppe Carleo. ``Variational quantum time evolution without the quantum geometric tensor''. Physical Review Research 6 (2024).
https://doi.org/10.1103/physrevresearch.6.013143

[18] Shun-ichi Amari. ``Natural gradient works efficiently in learning''. Neural Computation 10, 251–276 (1998).
https://doi.org/10.1162/089976698300017746

[19] Johannes Jakob Meyer. ``Fisher information in noisy intermediate-scale quantum applications''. Quantum 5, 539 (2021).
https://doi.org/10.22331/q-2021-09-09-539

[20] Tobias Haug, Kishor Bharti, and M.S. Kim. ``Capacity and quantum geometry of parametrized quantum circuits''. PRX Quantum 2 (2021).
https://doi.org/10.1103/prxquantum.2.040309

[21] Tobias Haug and M.S. Kim. ``Generalization of quantum machine learning models using quantum fisher information metric''. Physical Review Letters 133 (2024).
https://doi.org/10.1103/physrevlett.133.050603

[22] Tobias Haug and M. S. Kim. ``Natural parametrized quantum circuit''. Physical Review A 106 (2022).
https://doi.org/10.1103/physreva.106.052611

[23] Bálint Koczor and Simon C. Benjamin. ``Quantum natural gradient generalized to noisy and nonunitary circuits''. Physical Review A 106 (2022).
https://doi.org/10.1103/physreva.106.062416

[24] Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nature Physics 16, 1050–1057 (2020).
https://doi.org/10.1038/s41567-020-0932-7

[25] Stefan H. Sack, Raimel A. Medina, Alexios A. Michailidis, Richard Kueng, and Maksym Serbyn. ``Avoiding barren plateaus using classical shadows''. PRX Quantum 3 (2022).
https://doi.org/10.1103/prxquantum.3.020365

[26] Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, and Peter Zoller. ``The randomized measurement toolbox''. Nature Reviews Physics 5, 9–24 (2022).
https://doi.org/10.1038/s42254-022-00535-2

[27] Angus Lowe, Matija Medvidović, Anthony Hayes, Lee J. O'Riordan, Thomas R. Bromley, Juan Miguel Arrazola, and Nathan Killoran. ``Fast quantum circuit cutting with randomized measurements''. Quantum 7, 934 (2023).
https://doi.org/10.22331/q-2023-03-02-934

[28] Min Yu, Dongxiao Li, Jingcheng Wang, Yaoming Chu, Pengcheng Yang, Musang Gong, Nathan Goldman, and Jianming Cai. ``Experimental estimation of the quantum fisher information from randomized measurements''. Physical Review Research 3 (2021).
https://doi.org/10.1103/physrevresearch.3.043122

[29] Stephen J. Wright. ``Coordinate descent algorithms'' (2015). arXiv:1502.04759.
arXiv:1502.04759

[30] Yu. Nesterov. ``Efficiency of coordinate descent methods on huge-scale optimization problems''. SIAM Journal on Optimization 22, 341–362 (2012). arXiv:https://doi.org/10.1137/100802001.
https://doi.org/10.1137/100802001
arXiv:https://doi.org/10.1137/100802001

[31] Paul Tseng. ``Convergence of a block coordinate descent method for nondifferentiable minimization''. Journal of optimization theory and applications 109, 475–494 (2001).
https://doi.org/10.1023/A:1017501703105

[32] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. ``Improving variational quantum optimization using cvar''. Quantum 4, 256 (2020).
https://doi.org/10.22331/q-2020-04-20-256

[33] Ioannis Kolotouros and Petros Wallden. ``Evolving objective function for improved variational quantum optimization''. Phys. Rev. Res. 4, 023225 (2022).
https://doi.org/10.1103/PhysRevResearch.4.023225

[34] Li Li, Minjie Fan, Marc Coram, Patrick Riley, and Stefan Leichenauer. ``Quantum optimization with a novel gibbs objective function and ansatz architecture search''. Physical Review Research 2 (2020).
https://doi.org/10.1103/physrevresearch.2.023074

[35] Eric R. Anschuetz and Bobak T. Kiani. ``Quantum variational algorithms are swamped with traps''. Nature Communications 13 (2022).
https://doi.org/10.1038/s41467-022-35364-5

[36] Elena Alexandra Morozova and Nikolai Nikolaevich Chentsov. ``Markov invariant geometry on manifolds of states''. Journal of Soviet Mathematics 56, 2648–2669 (1991).
https://doi.org/10.1007/BF01095975

[37] Jonathan Romero, Ryan Babbush, Jarrod R. McClean, Cornelius Hempel, Peter Love, and Alán Aspuru-Guzik. ``Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz'' (2018). arXiv:1701.02691.
arXiv:1701.02691

[38] Dénes Petz. ``Monotone metrics on matrix spaces''. Linear Algebra and its Applications 244, 81–96 (1996).
https://doi.org/10.1016/0024-3795(94)00211-8

[39] 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

[40] Stephen Boyd and Lieven Vandenberghe. ``Convex optimization''. Cambridge University Press. (2004). url: https://www.cambridge.org/highereducation/books/convex-optimization/17D2FAA54F641A2F62C7CCD01DFA97C4.
https://www.cambridge.org/highereducation/books/convex-optimization/17D2FAA54F641A2F62C7CCD01DFA97C4

[41] David Wierichs, Christian Gogolin, and Michael Kastoryano. ``Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer''. Physical Review Research 2 (2020).
https://doi.org/10.1103/physrevresearch.2.043246

[42] Diego García-Martín, Martín Larocca, and M. Cerezo. ``Effects of noise on the overparametrization of quantum neural networks''. Physical Review Research 6 (2024).
https://doi.org/10.1103/physrevresearch.6.013295

[43] Naoki Yamamoto. ``On the natural gradient for variational quantum eigensolver'' (2019). arXiv:1909.05074.
arXiv:1909.05074

[44] Neal Parikh and Stephen P. Boyd. ``Proximal algorithms''. Found. Trends Optim. 1, 127–239 (2013). url: https://api.semanticscholar.org/CorpusID:51791656.
https://api.semanticscholar.org/CorpusID:51791656

[45] Samuel L. Braunstein and Carlton M. Caves. ``Statistical distance and the geometry of quantum states''. Phys. Rev. Lett. 72, 3439–3443 (1994).
https://doi.org/10.1103/PhysRevLett.72.3439

[46] Jing Liu, Haidong Yuan, Xiao-Ming Lu, and Xiaoguang Wang. ``Quantum fisher information matrix and multiparameter estimation''. Journal of Physics A: Mathematical and Theoretical 53, 023001 (2019).
https://doi.org/10.1088/1751-8121/ab5d4d

[47] Luca Pezzè, Mario A. Ciampini, Nicolò Spagnolo, Peter C. Humphreys, Animesh Datta, Ian A. Walmsley, Marco Barbieri, Fabio Sciarrino, and Augusto Smerzi. ``Optimal measurements for simultaneous quantum estimation of multiple phases''. Phys. Rev. Lett. 119, 130504 (2017).
https://doi.org/10.1103/PhysRevLett.119.130504

[48] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner. ``Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information''. Quantum 5, 567 (2021).
https://doi.org/10.22331/q-2021-10-20-567

[49] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. ``Quantum approximate optimization algorithm for maxcut: A fermionic view''. Physical Review A 97 (2018).
https://doi.org/10.1103/physreva.97.022304

[50] Gavin E. Crooks. ``Performance of the quantum approximate optimization algorithm on the maximum cut problem'' (2018). arXiv:1811.08419.
arXiv:1811.08419

[51] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. ``Obstacles to variational quantum optimization from symmetry protection''. Physical Review Letters 125 (2020).
https://doi.org/10.1103/physrevlett.125.260505

[52] Giacomo Nannicini. ``Performance of hybrid quantum-classical variational heuristics for combinatorial optimization''. Physical Review E 99 (2019).
https://doi.org/10.1103/physreve.99.013304

[53] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. ``The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size''. Quantum 6, 759 (2022).
https://doi.org/10.22331/q-2022-07-07-759

[54] Andrew Lucas. ``Ising formulations of many np problems''. Frontiers in Physics 2 (2014).
https://doi.org/10.3389/fphy.2014.00005

[55] Barnaby van Straaten and Bálint Koczor. ``Measurement cost of metric-aware variational quantum algorithms''. PRX Quantum 2 (2021).
https://doi.org/10.1103/prxquantum.2.030324

Cited by

[1] Dwi Cahyo Mariyanto, Hadyan L. Prihadi, Angga Dito Fauzi, L. T. Handoko, Yanoar P. Sarwono, and Rui‐Qin Zhang, "Fubini‐Study Metric Tensor Evolution and Reduced State Distinguishability in Geometry‐Aware Optimization for Reliable Near‐Term Variational Quantum Eigensolvers", International Journal of Quantum Chemistry 126 13, e70255 (2026).

[2] Mezbah Uddin Rafi, "Quantum Natural Gradient Optimization for Convergence Reliability in NISQ Variational Quantum Algorithms", (2026).

[3] Rodica Ioana Lung and Florin Sebastian Duma, "A Noisy Optimization mechanism for variational quantum classifiers", Knowledge-Based Systems 340, 115659 (2026).

[4] Ioannis Kolotouros, David Joseph, and Anand Kumar Narayanan, "Accelerating quantum imaginary-time evolution with random measurements", Physical Review A 111 1, 012424 (2025).

[5] Mourad Halla, "Modified conjugate quantum natural gradient", EPJ Quantum Technology 12 1, 123 (2025).

[6] Nawres A. Alwan, Suzan J. Obaiys, Nadia M. G. Al-Saidi, and Rayane Chadli, Lecture Notes in Computer Science 16758, 284 (2027) ISBN:978-3-032-30496-4.

[7] Mourad Halla, "Quantum natural gradient with geodesic corrections for small shallow quantum circuits", Physica Scripta 100 5, 055121 (2025).

[8] Boniface Yogendran, Daniel Charlton, Miriam Beddig, Ioannis Kolotouros, and Petros Wallden, "Big data applications on small quantum computers", arXiv:2402.01529, (2024).

[9] Ioannis Kolotouros, Ioannis Petrongonas, Miloš Prokop, and Petros Wallden, "Simulating adiabatic quantum computing with parameterized quantum circuits", Quantum Science and Technology 10 1, 015003 (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 00:38:44) and SAO/NASA ADS (last updated successfully 2026-08-09 00:38:45). 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.