Computational complexity of projected entangled pair states
Open accessAbstract
We determine the computational power of preparing projected entangled pair states (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows us to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows us to use existing results from quantum complexity.
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.
Integrity signals
Registry
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.
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?
Contraction of PEPS in 2D and higher is #P-complete, and in practically interesting cases it relies on heuristic contraction schemes.
“Unfortunately the contraction of PEPS in 2D and higher is #P -complete 52 , and in practically interesting cases it relies on heuristic contraction schemes (lattice contraction is described in Sec.III B 1).”
From Beyond-classical computation in quantum simulation (2025) · cites this paper as [52]
PEPS exact contraction is #P-complete in general.
“Inference from PEPS representation, or its exact contraction, is known to be a #P -complete problem in general 52,53 .”
From Beyond-classical computation in quantum simulation (2025) · cites this paper as [52]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 15 · Cited by 313
Research works printed but not linked: 18
- S. R. White, Phys. Rev. Lett. 69, 2863 (1992).
- U. Schollwo ¨ck, Rev. Mod. Phys. 77, 259 (2005).
- D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, quant-ph/0608197. · arXiv
- F. Verstraete and J. I. Cirac, cond-mat/0407066. · arXiv
- C. Scho ¨n, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf, Phys. Rev. Lett. 95, 110503 (2005).
- G. Vidal, Phys. Rev. Lett. 91, 147902 (2003).
- F. Verstraete, M. M. Wolf, D. Perez-Garcia, and J. I. Cirac, Phys. Rev. Lett. 96, 220601 (2006).
- S. Aaronson, Proc. R. Soc. A 461, 3473 (2005).
- F. Verstraete and J. I. Cirac, Phys. Rev. A 70, 060302 (2004).
- R. Raussendorf and H. J. Briegel, Phys. Rev. Lett. 86, 5188 (2001);
- R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003).
- C. M. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, MA, 1994).
- S. Aaronson, Theory of Computing 1, 1 (2005).
- Y. Shi, Quantum Inf. Comput. 3, 84 (2003).
- D. Aharonov, quant-ph/0301040. · arXiv
- C. M. Dawson et al., Quantum Inf. Comput. 5, 102 (2005).
- D. Aharonov and T. Naveh, quant-ph/0210077. · arXiv
- R. Oliveira and B. M. Terhal, quant-ph/0504050. · arXiv
- Authors
- Schuch, N., Wolf, M. M., Verstraete, F., & Cirac, J. I.
- Affiliations
- Max Planck Society (DE)
- University of Vienna (AT)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2007-04-04
- Volume
- 98
- Issue
- 14
- Pages
- 140506-140506
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1964713133
- Cited by
- 313
- References
- 15
- Citations by year
- 2026: 26 · 2025: 34 · 2024: 29 · 2023: 26 · 2022: 19 · 2021: 32 · 2020: 25 · 2019: 16 · 2018: 10 · 2017: 10 · 2016: 8 · 2015: 14 · 2014: 10 · 2013: 9 · 2012: 11
- FWCI
- 5.71
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review Letters (publishedVersion)
- arXiv (Cornell University) (publishedVersion)
- PubMed (publishedVersion)
- Ghent University Academic Bibliography (Ghent University) (submittedVersion, other-oa)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Max Planck Institute for Plasma Physics (submittedVersion)
- MPG.PuRe (Max Planck Society) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Deutsche Forschungsgemeinschaft
- Elitenetzwerk Bayern
- Topics
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- projected entangled pair states, tensor network contraction, computational complexity, #P-completeness, post-selection, gapped Hamiltonians, ground state approximation, quantum complexity
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
