CoChat
Sign Up
Cited by 62Quantum many-body systemsQuantum Computing Algorithms and ArchitectureComplexity and Algorithms in Graphs

Contracting projected entangled pair states is average-case hard

Open access
Haferkamp, Jonas, Hangleiter, Dominik, Eisert, Jens, Gluza, Marek·2020·Physical Review Research
DOI 10.1103/physrevresearch.2.013010
Open this paper in CoChat — free accountOpen PDF

Abstract

This work shows that contraction of tensor networks is average-case hard, which means that the computation of expectation values is on average as hard as for specific configurations of highest computational hardness. This result is a stepping stone to the development of numerical algorithms to simulate strongly correlated quantum matter and at the same time contributes to the body of results on average-case hardness of physically relevant computational problems.

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

Crossref · 10.1103/physrevresearch.2.013010

Cites

6 of 6 references verified0 citation errors · 0 not checkable

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?

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

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

Flagged first, then by citations

Research works printed but not linked: 79

  1. A. Altland and B. D. Simons, Condensed Matter Field Theory (Cambridge University Press, Cambridge, UK, 2010).
  2. Y. V. Nazarov and Y. M. Blanter, Quantum Transport: Introduc- tion to Nanoscience (Cambridge University Press, Cambridge, UK, 2009).
  3. A. Acin, I. Bloch, H. Buhrman, T. Calarco, C. Eichler, J. Eisert, D. Esteve, N. Gisin, S. J. Glaser, F. Jelezko, S. Kuhr, M. Lewenstein, M. F. Riedel, P. O. Schmidt, R. Thew, A. Wallraff, I. Walmsley, and F. K. Wilhelm, The European quantum tech- nologies roadmap, New J. Phys. 20, 080201 (2018). · DOI
  4. F. Weber, Strange quark matter and compact stars, Prog. Part. Nucl. Phys. 54, 193 (2005). · DOI
  5. I. Arsene, I. Bearden, D. Beavis, C. Besliu, B. Budick, H. Bøggild, C. Chasman, C. Christensen, P. Christiansen, J. Cibor et al., Quark-gluon plasma and color glass condensate at RHIC? The perspective from the BRAHMS experiment, Nucl. Phys. A 757, 1 (2005). · DOI
  6. A. Georges, G. Kotliar, W. Krauth, and M. J. Rozenberg, Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions, Rev. Mod. Phys. 68, 13 (1996). · DOI · Paper page
  7. E. Gull, A. J. Millis, A. I. Lichtenstein, A. N. Rubtsov, M. Troyer, and P. Werner, Continuous-time Monte Carlo methods for quantum impurity models, Rev. Mod. Phys. 83, 349 (2011). · DOI
  8. W. Metzner, M. Salmhofer, C. Honerkamp, V. Meden, and K. Schönhammer, Functional renormalization group approach to correlated fermion systems, Rev. Mod. Phys. 84, 299 (2012). · DOI
  9. U. Schollwöck, The density-matrix renormalization group in the age of matrix product states, Ann. Phys. 326, 96 (2011). · DOI · Paper page
  10. F. Alet and N. Laflorencie, Many-body localization: An intro- duction and selected topics, C. R. Phys. 19, 498 (2018). · DOI
  11. T. DeGrand and C. DeTar, Lattice Methods for Quantum Chro- modynamics (World Scientific, Singapore, 2006).
  12. M. Fannes, B. Nachtergaele, and R. F. Werner, Finitely corre- lated states on quantum spin chains, Commun. Math. Phys. 144, 443 (1992). · DOI · Paper page
  13. F. Verstraete, V. Murg, and J. I. Cirac, Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems, Adv. Phys. 57, 143 (2008). · DOI
  14. R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Ann. Phys. 349, 117 (2014). · DOI · Paper page
  15. J. C. Bridgeman and C. T. Chubb, Hand-waving and interpretive dance: an introductory course on tensor networks, J. Phys. A 50, 223001 (2017). · DOI
  16. J. Eisert, M. Cramer, and M. B. Plenio, Area laws for the entanglement entropy, Rev. Mod. Phys. 82, 277 (2010). · DOI · Paper page
  17. F. Verstraete, J. J. Garcia-Ripoll, and J. I. Cirac, Matrix Product Density Operators: Simulation of Finite-Temperature and Dis- sipative Systems, Phys. Rev. Lett. 93, 207204 (2004). · DOI · Paper page
  18. D. Gobert, C. Kollath, U. Schollwöck, and G. Schütz, Real- time dynamics in spin-1/2 chains with adaptive time-dependent density matrix renormalization group, Phys. Rev. E 71, 036102 (2005). · DOI
  19. F. Verstraete and J. I. Cirac, Matrix product states rep- resent ground states faithfully, Phys. Rev. B 73, 094423 (2006). · DOI · Paper page
  20. S. R. Manmana, S. Wessel, R. M. Noack, and A. Muramatsu, Strongly Correlated Fermions After a Quantum Quench, Phys. Rev. Lett. 98, 210405 (2007). · DOI
  21. S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch, Probing the relaxation towards equilibrium in an isolated strongly correlated one- dimensional Bose gas, Nat. Phys. 8, 325 (2012). · DOI · Paper page
  22. T. Fukuhara, A. Kantian, M. Endres, M. Cheneau, P. Schauß, S. Hild, D. Bellem, U. Schollwöck, T. Giamarchi, C. Gross et al., Quantum dynamics of a mobile spin impurity, Nat. Phys. 9, 235 (2013). · DOI
  23. F. Pollmann, A. M. Turner, E. Berg, and M. Oshikawa, En- tanglement spectrum of a topological phase in one dimension, Phys. Rev. B 81, 064439 (2010). · DOI · Paper page
  24. J. H. Bardarson, F. Pollmann, and J. E. Moore, Unbounded Growth of Entanglement in Models of Many-Body Localiza- tion, Phys. Rev. Lett. 109, 017202 (2012). · DOI
  25. C. Karrasch, J. H. Bardarson, and J. E. Moore, Finite- Temperature Dynamical Density Matrix Renormalization Group and the Drude Weight of Spin-1/2 Chains, Phys. Rev. Lett. 108, 227206 (2012). · DOI
  26. T. Prosen, Open X X Z Spin Chain: Nonequilibrium Steady State and a Strict Bound on Ballistic Transport, Phys. Rev. Lett. 106, 217206 (2011). · DOI
  27. J. P. Ronzheimer, M. Schreiber, S. Braun, S. S. Hodgman, S. Langer, I. P. McCulloch, F. Heidrich-Meisner, I. Bloch, and U. Schneider, Expansion Dynamics of Interacting Bosons in Homogeneous Lattices in One and Two Dimensions, Phys. Rev. Lett. 110, 205301 (2013). · DOI
  28. I. Arad, Z. Landau, U. Vazirani, and T. Vidick, Rigorous RG algorithms and area laws for low energy eigenstates in 1D, Commun. Math. Phys. 356, 65 (2017). · DOI
  29. D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Matrix product state representations, Quantum Inf. Comput. 7, 401 (2007).
  30. F. Verstraete, M. M. Wolf, D. Perez-Garcia, and J. I. Cirac, Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States, Phys. Rev. Lett. 96, 220601 (2006). · DOI · Paper page
  31. N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, The Com- putational Complexity of PEPS, Phys. Rev. Lett. 98, 140506 (2007). · DOI · Paper page
  32. M. A. Nielsen and I. Chuang, Quantum Computation and Quan- tum Information (Cambridge University Press, Cambridge, UK, 2002).
  33. S. Aaronson, Quantum Computing Since Democritus (Cambridge University Press, Cambridge, UK, 2013).
  34. D. Lokshtanov, D. Marx, and S. Saurabh, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 105, 41 (2011).
  35. F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. A 15, 3241 (1982). · DOI
  36. J. Feigenbaum and L. Fortnow, On the random-self-reducibility of complete sets, in Proceedings of the Sixth Annual Structure in Complexity Theory Conference (IEEE, Piscataway, NJ, 1991).
  37. S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Theor. Comput. 9, 143 (2013). · DOI
  38. A. Bouland, B. Feffermann, C. Nirkhe, and U. Vazirani, Quan- tum supremacy and the complexity of random circuit sampling, Nat. Phys. 15, 159 (2019). · DOI · Paper page
  39. Y.-Y. Shi, L.-M. Duan, and G. Vidal, Classical simulation of quantum many-body systems with a tree tensor network, Phys. Rev. A 74, 022320 (2006). · DOI · Paper page
  40. A. Anshu, I. Arad, and A. Jain, How local is the information in tensor networks of matrix product states or projected entangled pairs states, Phys. Rev. B 94, 195143 (2016). · DOI
  41. M. Schwarz, O. Buerschaper, and J. Eisert, Approximating local observables on projected entangled pair states, Phys. Rev. A 95, 060102(R) (2017). · DOI
  42. M. Lubasch, J. I. Cirac, and M.-C. Banuls, Unifying projected entangled pair states contractions, New J. Phys. 16, 033014 (2014). · DOI
  43. M. Levin and C. P. Nave, Tensor Renormalization Group Approach to Two-Dimensional Classical Lattice Models, Phys. Rev. Lett. 99, 120601 (2007). · DOI
  44. Z.-C. Gu and X.-G. Wen, Tensor-entanglement-filtering renor- malization approach and symmetry-protected topological order, Phys. Rev. B 80, 155131 (2009). · DOI
  45. Z. Y. Xie, H. C. Jiang, Q. N. Chen, Z. Y. Weng, and T. Xiang, Second Renormalization of Tensor-Network States, Phys. Rev. Lett. 103, 160601 (2009). · DOI
  46. H. H. Zhao, Z. Y. Xie, Q. N. Chen, Z. C. Wei, J. W. Cai, and T. Xiang, Renormalization of tensor-network states, Phys. Rev. B 81, 174411 (2010). · DOI
  47. S. Yang, Z.-C. Gu, and X.-G. Wen, Loop Optimization for Tensor Network Renormalization, Phys. Rev. Lett. 118, 110504 (2017). · DOI
  48. G. Evenbly, Algorithms for tensor network renormalization, Phys. Rev. B 95, 045117 (2017). · DOI
  49. F. Verstraete and J. I. Cirac, Renormalization algorithms for quantum-many body systems in two and higher dimensions, arXiv:cond-mat/0407066. · arXiv
  50. R. Orús and G. Vidal, Infinite time-evolving block decimation algorithm beyond unitary evolution, Phys. Rev. B 78, 155117 (2008). · DOI
  51. L. Vanderstraeten, J. Haegeman, P. Corboz, and F. Verstraete, Gradient methods for variational optimization of projected entangled-pair states, Phys. Rev. B 94, 155123 (2016). · DOI · Paper page
  52. M. T. Fishman, L. Vanderstraeten, V. Zauner-Stauber, J. Haegeman, and F. Verstraete, Faster methods for contract- ing infinite 2D tensor networks, Phys. Rev. B 98, 235148 (2018). · DOI · Paper page
  53. T. Nishino, Density matrix renormalization group method for 2D classical models, J. Phys. Soc. Jpn. 64, 3598 (1995). · DOI
  54. T. Nishino, K. Okunishi, and M. Kikuchi, Numerical renormal- ization group at criticality, Phys. Lett. A 213, 69 (1996). · DOI
  55. T. Nishino and K. Okunishi, Corner transfer matrix algorithm for classical renormalization group, J. Phys. Soc. Jpn. 66, 3040 (1997). · DOI
  56. R. Orús, Exploring corner transfer matrices and corner ten- sors for the classical simulation of quantum lattice systems, Phys. Rev. B 85, 205117 (2012). · DOI
  57. A. Kshetrimayum, M. Rizzi, J. Eisert, and R. Orús, A Tensor Network Annealing Algorithm for Two-Dimensional Thermal States, Phys. Rev. Lett. 122, 070502 (2019). · DOI
  58. I. Markov and Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM J. Comp. 38, 963 (2008). · DOI · Paper page
  59. I. Arad and Z. Landau, Quantum computation and the evalua- tion of tensor networks, SIAM J. Comp. 39, 3089 (2010). · DOI
  60. S.-J. Ran, E. Tirrito, C. Peng, X. Chen, L. Tagliacozzo, G. Su, and M. Lewenstein, Tensor Network Contractions: Methods and Applications to Quantum Many-Body Systems, Lecture Notes in Physics, Vol. 964 (Springer, 2000).
  61. P. Corboz, R. Orús, B. Bauer, and G. Vidal, Simulation of strongly correlated fermions in two spatial dimensions with fermionic projected entangled-pair states, Phys. Rev. B 81, 165104 (2010). · DOI
  62. P. Corboz, S. R. White, G. Vidal, and M. Troyer, Stripes in the two-dimensional t-J model with infinite projected entangled- pair states, Phys. Rev. B 84, 041108(R) (2011). · DOI · Paper page
  63. I. Niesen and P. Corboz, A tensor network study of the complete ground state phase diagram of the spin-1 bilinear-biquadratic Heisenberg model on the square lattice, SciPost Phys. 3, 030 (2017). · DOI
  64. Y. H. Matsuda, N. Abe, S. Takeyama, H. Kageyama, P. Corboz, A. Honecker, S. R. Manmana, G. R. Foltin, K. P. Schmidt, and F. Mila, Magnetization of SrCu 2 (BO 3 ) 2 in Ultrahigh Magnetic Fields up to 118 T, Phys. Rev. Lett. 111, 137204 (2013). · DOI
  65. A. Kshetrimayum, T. Picot, R. Orús, and D. Poilblanc, Spin- 1/2 kagome XXZ model in a field: Competition between lattice nematic and solid orders, Phys. Rev. B 94, 235146 (2016). · DOI
  66. S. Yan, D. A. Huse, and S. R. White, Spin-liquid ground state of the S = 1/2 Kagome Heisenberg antiferromagnet, Science 332, 1173 (2011). · DOI
  67. D. Poilblanc, J. I. Cirac, and N. Schuch, Chiral topological spin liquids with projected entangled pair states, Phys. Rev. B 91, 224431 (2015). · DOI
  68. T. Picot, M. Ziegler, R. Orús, and D. Poilblanc, Spin-S kagome quantum antiferromagnets in a field with tensor networks, Phys. Rev. B 93, 060407(R) (2016). · DOI
  69. H. J. Liao, Z. Y. Xie, J. Chen, Z. Y. Liu, H. D. Xie, R. Z. Huang, B. Normand, and T. Xiang, Gapless Spin-Liquid Ground State in the S = 1/2 Kagome Antiferromagnet, Phys. Rev. Lett. 118, 137202 (2017). · DOI
  70. J.-Y. Chen, L. Vanderstraeten, S. Capponi, and D. Poilblanc, Non-Abelian chiral spin liquid in a quantum antiferromagnet revealed by an iPEPS study, Phys. Rev. B 98, 184409 (2018). · DOI
  71. T. B. Wahl, A. Pal, and S. H. Simon, Efficient Representation of Fully Many-Body Localized Systems Using Tensor Networks, Phys. Rev. X 7, 021018 (2017). · DOI
  72. S. Bachmann, S. Michalakis, B. Nachtergaele, and R. Sims, Automorphic equivalence within gapped phases of quantum lattice systems, Commun. Math. Phys. 309, 835 (2012). · DOI
  73. M. B. Hastings, Quasi-adiabatic continuation for disordered systems: Applications to correlations, Lieb-Schultz-Mattis, and Hall conductance, arXiv:1001.5280. · arXiv
  74. R. Raussendorf and H. J. Briegel, A One-Way Quantum Com- puter, Phys. Rev. Lett. 86, 5188 (2001). · DOI · Paper page
  75. L. G. Valiant, Quantum cicuits that can be simulated classically in polynomial time, SIAM Comput. 31, 1229 (1979). · DOI · Paper page
  76. R. Paturi, On the degree of polynomials that approximate sym- metric Boolean functions, in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (ACM Press, New York, 1992), pp. 468-474.
  77. E. A. Rakhmanov, Bounds for polynomials with a unit discrete norm, Ann. Math. 165, 55 (2007). · DOI
  78. L. Welch and E. Berlekamp, Error correction for algbraic block codes, US Patent, 4,633,470 (1986).
  79. R. Movassagh, Efficient unitary paths and quantum computa- tional supremacy: A proof of average-case hardness of Random Circuit Sampling, arXiv:1810.04681. · arXiv

Cited by

Sorted by citations

Authors
Haferkamp, J., Hangleiter, D., Eisert, J., & Gluza, M.
Affiliations
Freie Universität Berlin (DE)
Venue
Physical Review Research
Publisher
American Physical Society (APS)
Published
2020-01-03
Volume
2
Issue
1
ISSN
2643-1564 (ISSN-L)
DOI
10.1103/physrevresearch.2.013010
OpenAlex
W2892488094
Cited by
62
References
6
Citations by year
2026: 6 · 2025: 13 · 2024: 11 · 2023: 6 · 2022: 6 · 2021: 11 · 2020: 7 · 2019: 2
FWCI
3.05
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical Review Research (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
  • Refubium (Universitätsbibliothek der Freien Universität Berlin) (submittedVersion, cc-by)
  • arXiv (Cornell University)
  • Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver (cc-by)
Funders
  • Deutsche Forschungsgemeinschaft (EI 519/14-1, EI 519/7-1, EI 519/15-1, CRC 183 B1)
  • European Research Council
  • John Templeton Foundation
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 › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
projected entangled pair states, tensor network contraction, average-case hardness, computational complexity, strongly correlated quantum matter, quantum simulation, numerical algorithms

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