CoChat
Sign Up
PreprintCited by 279Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

Obstacles to State Preparation and Variational Optimization from Symmetry Protection

Open access
Bravyi, Sergey, Kliesch, Alexander, Koenig, Robert, Tang, Eugene·2019·arXiv
DOI 10.48550/arxiv.1910.08980arXiv 1910.08980
Open this paper in CoChat — free accountOpen PDF

Abstract

Local Hamiltonians with topological quantum order exhibit highly entangled ground states that cannot be prepared by shallow quantum circuits. Here, we show that this property may extend to all low-energy states in the presence of an on-site $\mathbb{Z}_2$ symmetry. This proves a version of the No Low-Energy Trivial States (NLTS) conjecture for a family of local Hamiltonians with symmetry protected topological order. A surprising consequence of this result is that the Goemans-Williamson algorithm outperforms the Quantum Approximate Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant level. We argue that the locality and symmetry of QAOA severely limits its performance. To overcome these limitations, we propose a non-local version of QAOA, and give numerical evidence that it significantly outperforms standard QAOA for frustrated Ising models on random 3-regular graphs.

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.1910.08980

Cites

Statistics

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?

  • When RQAOA is run with the QAOA subroutine of depth p=1, it can be efficiently simulated on a classical computer, which can serve as an important benchmark with classical algorithms.

    “When RQAOAis run with the QAOA subroutine of depth p = 1 , it can efficiently simulated on a classical computer, which can serve as an important benchmark with classical algorithms (Bravyi et al. , 2019).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Bravyi et al. , 2019

    The Additional information section reports a numerical comparison of level-1 RQAOA with the classical Goemans–Williamson algorithm and says the authors used an algorithm to compute the needed correlations. It does not state that level-1 RQAOA as a whole can be efficiently simulated on a classical computer; the benchmark rationale therefore lacks support. (LLM, conf=0.79)

    Experimental — accuracy not yet measured

  • For specific instances of the Max-Cut problem, QAOA for p=1 was shown to perform equally well or worse than classical algorithms.

    “For specific instances of the Max-Cut problem, QAOA for p = 1 was shown to perform equally well or worse than classical algorithms (Bravyi et al. , 2019; Hastings, 2019).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Bravyi et al., 2019

  • A non-local version of QAOA called recursive QAOA (RQAOA) was proposed.

    “Recently, a non-local version of QAOA called recursive QAOA (RQAOA) was proposed (Bravyi et al. , 2019).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Bravyi et al. , 2019

Self-check

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

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

Cites

No references could be resolved yet.

Research works printed but not linked: 25

  1. A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'Brien, Nat. Commun. 5, 4213 (2014). · DOI · Paper page
  2. A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Nature (London) 549, 242 (2017). · DOI · Paper page
  3. E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028. · arXiv
  4. A. Y. Kitaev, Ann. Phys. (Amsterdam) 303, 2 (2003). · DOI · Paper page
  5. S. Bravyi, M. B. Hastings, and F. Verstraete, Phys. Rev. Lett. 97, 050401 (2006). · DOI · Paper page
  6. D. Aharonov and Y. Touati, arXiv:1810.03912. · arXiv
  7. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Nat. Commun. 9, 4812 (2018). · DOI · Paper page
  8. E. Farhi and A. W. Harrow, arXiv:1602.07674. · arXiv
  9. M. X. Goemans and D. P. Williamson, J. ACM 42, 1115 (1995). · DOI · Paper page
  10. R. Shaydulin and Y. Alexeev, Evaluating quantum approxi- mate optimization algorithm: A case study, in 2019 Tenth International Green and Sustainable Computing Conference (IGSC) (IEEE, New York, 2019), pp. 1-6.
  11. M. B. Hastings, arXiv:1905.07047. · arXiv
  12. Z.-C. Gu and X.-G. Wen, Phys. Rev. B 80, 155131 (2009). · DOI
  13. N. Schuch, D. Pérez-García, and I. Cirac, Phys. Rev. B 84, 165139 (2011). · DOI
  14. F. Pollmann, A. M. Turner, E. Berg, and M. Oshikawa, Phys. Rev. B 81, 064439 (2010). · DOI · Paper page
  15. A. W. Marcus, D. A. Spielman, and N. Srivastava, Interlac- ing families iv: Bipartite Ramanujan graphs of all sizes, in Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (IEEE, New York, 2015), pp. 1358-1377.
  16. A. W. Marcus, D. A. Spielman, and N. Srivastava, Ann. Math. 182, 307 (2015). · DOI
  17. M. Morgenstern, J. Comb. Theory Ser. B 62, 44 (1994). · DOI
  18. J. Friedman, arXiv:cs/0405020. · arXiv
  19. L. Eldar and A. W. Harrow, Local Hamiltonians whose ground states are hard to approximate, in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, New York, 2017), pp. 427-438.
  20. See Supplemental Material at http://link.aps.org/ supplemental/10.1103/PhysRevLett.125.260505 for further details on state preparation and implementation. · DOI · Paper page
  21. G. Mbeng, R. Fazio, and G. Santoro, arXiv:1906.08948. · arXiv
  22. F. Barahona, J. Phys. A 15, 3241 (1982). · DOI
  23. Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Phys. Rev. A 97, 022304 (2018). · DOI · Paper page
  24. E. Farhi, D. Gamarnik, and S. Gutmann, arXiv:2004.09002. · arXiv
  25. E. Farhi, D. Gamarnik, and S. Gutmann, arXiv:2005.08747. · arXiv

Cited by

Sorted by citations

Authors
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E.
Affiliations
  • IBM (United States) (US)
  • Technical University of Munich (DE)
  • California Institute of Technology (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
125
Issue
26
Pages
260505-260505
ISSN
0031-9007 (ISSN-L)
DOI
10.48550/arxiv.1910.08980
arXiv
1910.08980
OpenAlex
W2980835754
Cited by
279
References
0
Citations by year
2026: 23 · 2025: 50 · 2024: 52 · 2023: 71 · 2022: 43 · 2021: 31 · 2020: 8 · 2019: 1
FWCI
15.04
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • Physical Review Letters (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion)
  • mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1733907)
  • Deutsche Forschungsgemeinschaft
  • Institute for Quantum Information and Matter, California Institute of Technology (PHY-1733907)
  • Natural Sciences and Engineering Research Council of Canada (PHY-1733907)
  • Army Research Office (W911NF-20-1-0014, W911NF)
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 › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
quantum approximate optimization algorithm, variational quantum optimization, symmetry protection, Goemans-Williamson algorithm, MaxCut, frustrated Ising model

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