CoChat
Sign Up
PreprintCited by 172Quantum Computing Algorithms and ArchitectureQuantum many-body systemsAdvanced Chemical Physics Studies

The DOI matches its DataCite record.

Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer

Open access
Wierichs, David, Gogolin, Christian, Kastoryano, Michael·2020·arXiv
DOI 10.48550/arxiv.2004.14666arXiv 2004.14666
Open this paper in CoChat — free accountOpen PDF

Abstract

We compare the BFGS optimizer, ADAM and Natural Gradient Descent (NatGrad) in the context of Variational Quantum Eigensolvers (VQEs). We systematically analyze their performance on the QAOA ansatz for the Transverse Field Ising Model (TFIM) as well as on overparametrized circuits with the ability to break the symmetry of the Hamiltonian. The BFGS algorithm is frequently unable to find a global minimum for systems beyond about 20 spins and ADAM easily gets trapped in local minima. On the other hand, NatGrad shows stable performance on all considered system sizes, albeit at a significantly higher cost per epoch. In sharp contrast to most classical gradient based learning, the performance of all optimizers is found to decrease upon seemingly benign overparametrization of the ansatz class, with BFGS and ADAM failing more often and more severely than NatGrad. Additional tests for the Heisenberg XXZ model corroborate the accuracy problems of BFGS in high dimensions, but they reveal some shortcomings of NatGrad as well. Our results suggest that great care needs to be taken in the choice of gradient based optimizers and the parametrization for VQEs.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2004.14666

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 58

  1. E. Farhi, J. Goldstone, and S. Gutmann, A quantum approxi- mate optimization algorithm, arXiv:1411.4028. · arXiv
  2. Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. Sawaya et al., Quantum chemistry in the age of quantum com- puting, Chem. Rev. 119, 10856 (2019). · DOI · Paper page
  3. A. Smith, M. S. Kim, F. Pollmann, and J. Knolle, Simulating quantum many-body dynamics on a current digital quantum computer, npj Quantum Inf. 5, 106 (2019). · DOI
  4. L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices, Phys. Rev. X 10, 021067 (2020). · DOI · Paper page
  5. D. P. Kingma and J. Ba, Adam: A method for stochastic opti- mization, arXiv:1412.6980. · arXiv
  6. S. Ruder, An overview of gradient descent optimization algo- rithms, arXiv:1609.04747. · arXiv
  7. M. Ostaszewski, E. Grant, and M. Benedetti, Quantum circuit structure learning, arXiv:1905.09692. · arXiv
  8. C. G. Broyden, The convergence of a class of double-rank min- imization algorithms 1. General considerations, IMA J. Appl. Math. 6, 76 (1970) · DOI
  9. R. Fletcher, A new approach to variable metric algorithms, Comput. J. 13, 317 (1970) . · DOI
  10. D. Goldfarb, A family of variable-metric methods derived by variational means, Math. Comput. 24, 23 (1970). · DOI
  11. D. F. Shanno, Conditioning of quasi-Newton methods for func- tion minimization, Math. Comput. 24, 647 (1970). · DOI
  12. G. Giacomo Guerreschi and M. Smelyanskiy, Practical optimization for hybrid quantum-classical algorithms, arXiv:1701.01450. · arXiv
  13. G. B. Mbeng, R. Fazio, and G. Santoro, Quantum annealing: A journey through digitalization, control, and hybrid quantum variational schemes, arXiv:1906.08948v3. · arXiv
  14. Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, XY mixers: Analytical and numerical results for the quan- tum alternating operator Ansatz, Phys. Rev. A 101, 012320 (2020). · DOI · Paper page
  15. H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, An adaptive variational algorithm for exact molecular sim- ulations on a quantum computer, Nat. Commun. 10, 3007 (2019). · DOI · Paper page
  16. J. Romero, R. Babbush, J. R. McClean, C. Hempel, P. J. Love, and A. Aspuru-Guzik, Strategies for quantum computing molecular energies using the unitary coupled cluster Ansatz, Quantum Sci. Tech. 4, 014008 (2018). · DOI · Paper page
  17. B. T. Gard, L. Zhu, G. S. Barron, N. J. Mayhall, S. E. Economou, and E. Barnes, Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver al- gorithm, npj Quantum Inf. 6, 10 (2020). · DOI · Paper page
  18. J. Stokes, J. Izaac, N. Killoran, and G. Carleo, Quantum natural gradient, Quantum 4, 269 (2020). · DOI · Paper page
  19. S.-I. Amari, Natural gradient works efficiently in learning, Neural Comput. 10, 251 (1998). · DOI
  20. A. Harrow and J. Napp, Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms, arXiv:1901.05374. · arXiv
  21. J. Martens and I. Sutskever, Training deep and recurrent net- works with hessian-free optimization, in Neural Networks: Tricks of the Trade (Springer, Berlin, Heidelberg, 2012), pp. 479-535.
  22. R. Livni, S. Shalev-Shwartz, and O. Shamir, On the compu- tational efficiency of training neural networks, in Advances in Neural Information Processing Systems (Curran Associates, Inc., New York, NY, 2014), pp. 855-863.
  23. D. Li, T. Ding, and R. Sun, Over-parameterized deep neural networks have no strict local minima for any continuous acti- vations, arXiv:1812.11039. · arXiv
  24. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nat. Commun. 9, 4812 (2018). · DOI · Paper page
  25. C.-Y. Park and M. J. Kastoryano, Geometry of learning neural quantum states, Phys. Rev. Res. 2, 023232 (2020). · DOI
  26. M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, and N. Killoran, Evaluating analytic gradients on quantum hardware, Phys. Rev. A 99, 032331 (2019). · DOI · Paper page
  27. H. Lun Tang, E. Barnes, H. R. Grimsley, N. J. Mayhall, and S. E. Economou, qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient Ansatze on a quantum pro- cessor, arXiv:1911.10205. · arXiv
  28. A. G. Rattew, S. Hu, M. Pistoia, R. Chen, and S. Wood, A domain-agnostic, noise-resistant, hardware-efficient evolution- ary variational quantum eigensolver, arXiv:1910.09694. · arXiv
  29. M. E. S. Morales, J. Biamonte, and Z. Zimborás, On the uni- versality of the quantum approximate optimization algorithm, Quantum Info. Process. 19, 291 (2020). · DOI
  30. S. Lloyd, Quantum approximate optimization is computation- ally universal, arXiv:1812.11075. · arXiv
  31. M. B. Hastings, Classical and quantum bounded depth approx- imation algorithms, arXiv:1905.07047. · arXiv
  32. E. Farhi and A. W. Harrow, Quantum Supremacy through the Quantum Approximate Optimization Algorithm, arXiv:1602.07674. · arXiv
  33. Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum approximation optimization algorithm for MaxCut: A fermionic view, Phys. Rev. A 97, 022304 (2018). · DOI · Paper page
  34. W. W. Ho and T. H. Hsieh, Efficient variational simulation of nontrivial quantum states, SciPost Physics 6, 029 (2019). · DOI · Paper page
  35. M. Y. Niu, S. Lu, and I. Chuang, Optimizing QAOA: Suc- cess probability and runtime dependence on circuit depth, arXiv:1905.12134. · arXiv
  36. V. Akshay, H. Philathong, M. E. Morales, and J. D. Biamonte, Reachability Deficits in Quantum Approximate Optimization, Phys. Rev. Lett. 124, 090504 (2020). · DOI · Paper page
  37. S. Hadfield, Z. Wang, B. O'Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate op- timization algorithm to a quantum alternating operator Ansatz, Algorithms 12, 34 (2019). · DOI · Paper page
  38. J. Duchi, E. Hazan, and Y. Singer, Adaptive subgradient meth- ods for online learning and stochastic optimization, J. Machine Learning Res. 12, 61 (2011).
  39. F. Becca and S. Sorella, Quantum Monte Carlo Approaches for Correlated Systems (Cambridge University Press, Cambridge, 2017).
  40. G. Carleo and M. Troyer, Solving the quantum many-body problem with artificial neural networks, Science 355, 602 (2017). · DOI · Paper page
  41. Y. Li and S. C. Benjamin, Efficient Variational Quantum Simu- lator Incorporating Active Error Minimization, Phys. Rev. X 7, 021050 (2017). · DOI · Paper page
  42. P.-L. Dallaire-Demers, J. Romero, L. Veis, S. Sim, and A. Aspuru-Guzik, Low-depth circuit Ansatz for preparing cor- related fermionic states on a quantum computer, Quantum Science Technology 4, 045005 (2019). · DOI · Paper page
  43. S. McArdle, T. Jones, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan, Variational Ansatz-based quantum simula- tion of imaginary time evolution, npj Quantum Inf. 5, 75 (2019). · DOI · Paper page
  44. B. Koczor and S. C. Benjamin, Quantum natural gradient gen- eralised to nonunitary circuits, arXiv:1912.08660. · arXiv
  45. N. Yamamoto, On the natural gradient for variational quantum eigensolver, 2019, arXiv:1909.05074. · arXiv
  46. K. M. Nakanishi, K. Fujii, and S. Todo, Sequential minimal op- timization for quantum-classical hybrid algorithms, Phys. Rev. Res. 2, 043158 (2020). · DOI · Paper page
  47. J. Li, X. Yang, X. Peng, and C.-P. Sun, Hybrid Quantum- Classical Approach to Quantum Optimal Control, Phys. Rev. Lett. 118, 150503 (2017). · DOI · Paper page
  48. K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Quantum circuit learning, Phys. Rev. A 98, 032309 (2018). · DOI · Paper page
  49. K. Mitarai and K. Fujii, Methodology for replacing indirect measurements with direct measurements, Phys. Rev. Res. 1, 013006 (2019). · DOI · Paper page
  50. J. C. Spall, Multivariate stochastic approximation using a si- multaneous perturbation gradient approximation, IEEE Trans. Autom. Control 37, 332 (1992). · DOI · Paper page
  51. P. Gokhale and F. T. Chong, O(N 3 ) measurement cost for variational quantum eigensolver on molecular hamiltonians, arXiv:1908.11857. · arXiv
  52. T.-C. Yen, V. Verteletskyi, and A. F. Izmaylov, Measuring all compatible operators in one series of single-qubit measure- ments using unitary transformations, J. Chem. Theory Comput. 16, 2400 (2020). · DOI · Paper page
  53. E. Lieb, T. Schultz, and D. Mattis, Two soluble models of an antiferromagnetic chain, Ann. Phys. 16, 407 (1961). · DOI
  54. M. Karbach, G. Müller, H. Gould, and J. Tobochnik, Introduc- tion to the bethe Ansatz i, Comput. Phys. 11, 36 (1997). · DOI
  55. M. Karbach, K. Hu, and G. Müller, Introduction to the bethe Ansatz ii, Comput. Phys. 12, 565 (1998). · DOI
  56. D. S. Steiger, T. Häner, and M. Troyer, Projectq: an open source software framework for quantum computing, Quantum 2, 49 (2018). · DOI · Paper page
  57. P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright et al., SciPy 1.0: Fundamental Algorithms for Scien- tific Computing in Python, Nat. Methods 17, 261 (2020). · DOI · Paper page
  58. B. van Straaten and B. Koczor, Measurement cost of metric- aware variational quantum algorithms, arXiv:2005.05172. · arXiv

Cited by

Metadata

Authors
Wierichs, D., Gogolin, C., & Kastoryano, M.
Affiliations
  • University of Cologne (DE)
  • Amazon (United States) (US)
ORCID
Wierichs, David
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
2
Issue
4
ISSN
2643-1564 (ISSN-L)
DOI
10.48550/arxiv.2004.14666
arXiv
2004.14666
OpenAlex
W3021584456
Cited by
172
References
0
Citations by year
2026: 13 · 2025: 22 · 2024: 29 · 2023: 50 · 2022: 27 · 2021: 22 · 2020: 8
FWCI
10.51
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical Review Research (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Deutsche Forschungsgemeinschaft (2004/1390534769, EXC 2004/1, EXC 2004/1 ‐ 390 534 769, 390534769)
  • Universität zu Köln
  • Covestro
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Advanced Chemical Physics Studies
Keywords
variational quantum eigensolver, natural gradient descent, local minima, quantum optimization, BFGS, Adam, overparameterization, transverse-field Ising model, XXZ model, symmetry breaking, spin chains

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review