Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1603.06049 · Physical review. B./Physical review. B

How local is the information in tensor networks of matrix product states or projected entangled pairs states

Anurag Anshu, Itai Arad, Aditya Jain

Published Nov 28, 2016• 10 citations
arXivHTMLPDF

Abstract

Two-dimensional tensor networks such as projected entangled pairs states (PEPS) are generally hard to contract. This is arguably the main reason why variational tensor network methods in two dimensions are still not as successful as in one dimension. However, this is not necessarily the case if the tensor network represents a gapped ground state of a local Hamiltonian; such states are subject to many constraints and contain much more structure. In this paper, we introduce an approach for approximating the expectation value of a local observable in ground states of local Hamiltonians that are represented by PEPS tensor networks. Instead of contracting the full tensor network, we try to estimate the expectation value using only a local patch of the tensor network around the observable. Surprisingly, we demonstrate that this is often easier to do when the system is frustrated. In such case, the spanning vectors of the local patch are subject to nontrivial constraints that can be utilized via a semidefinite program to calculate rigorous lower and upper bounds on the expectation value. We test our approach in one-dimensional systems, where we show how the expectation value can be calculated up to at least 3 or 4 digits of precision, even when the patch radius is smaller than the correlation length.

DOI
10.1103/physrevb.94.195143

Related papers

Approximating local observables on projected entangled pair states

M. Schwarz, Oliver Buerschaper, Jens Eisert

Tensor network states are for good reasons believed to capture ground states of gapped local Hamiltonians arising in the condensed matter context, states which are in turn expected to satisfy an entanglement area law. However, the computational hardness of contracting projected entangled pair states in two- and higher-dimensional systems is often seen as a significant obstacle when devising higher-dimensional variants of the density-matrix renormalization group method. In this work, we show that for those projected entangled pair states that are expected to provide good approximations of such ground states of local Hamiltonians, one can compute local expectation values in quasipolynomial time. We therefore provide a complexity-theoretic justification of why state-of-the-art numerical tools work so well in practice. We finally turn to the computation of local expectation values on quantum computers, providing a meaningful application for a small-scale quantum computer.

arXiv:1606.06301•Physical Review A•Jun 20, 2017•18 citations

Variational methods for contracting projected entangled-pair states

Laurens Vanderstraeten, Lander Burgelman, Boris Ponsioen +5 more

Projected entangled-pair states (PEPS) provide excellent variational wave functions for ground states of strongly correlated quantum systems in two dimensions. Determining the expectation value of such a PEPS wave function requires the contraction of a two-dimensional tensor network. Here, the authors show that this contraction can itself be formulated as a variational problem, allowing one to compare the accuracies of two commonly used contraction schemes. The authors find good agreement between the different schemes, demonstrating the robustness of PEPS simulations.

arXiv:2110.12726•Physical review. B./Physical review. B•May 25, 2022•26 citations

Unifying projected entangled pair state contractions

Michael Lubasch, J. I. Cirac, Mari Carmen Bañuls

The approximate contraction of a tensor network of projected entangled pair states (PEPS) is a fundamental ingredient of any PEPS algorithm, required for the optimization of the tensors in ground state search or time evolution, as well as for the evaluation of expectation values. An exact contraction is in general impossible, and the choice of the approximating procedure determines the efficiency and accuracy of the algorithm. We analyze different previous proposals for this approximation, and show that they can be understood via the form of their environment, i.e. the operator that results from contracting part of the network. This provides physical insight into the limitation of various approaches, and allows us to introduce a new strategy, based on the idea of clusters, that unifies previous methods. The resulting contraction algorithm interpolates naturally between the cheapest and most imprecise and the most costly and most precise method. We benchmark the different algorithms with finite PEPS, and show how the cluster strategy can be used for both the tensor optimization and the calculation of expectation values. Additionally, we discuss its applicability to the parallelization of PEPS and to infinite systems.

arXiv:1311.6696•New Journal of Physics•Mar 14, 2014•126 citations

Contracting projected entangled pair states is average-case hard

Jonas Haferkamp, Dominik Hangleiter, Jens Eisert +1 more

An accurate calculation of the properties of quantum many-body systems is one of the most important yet intricate challenges of modern physics and computer science. In recent years, the tensor network ansatz has established itself as one of the most promising approaches enabling striking efficiency of simulating static properties of one-dimensional systems and abounding numerical applications in condensed matter theory. In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P-complete. Therefore an efficient algorithm for PEPS contraction would allow solving exceedingly difficult combinatorial counting problems, which is considered highly unlikely. Due to the importance of understanding two- and three-dimensional systems the question currently remains: Are the known constructions typical of states relevant for quantum many-body systems? In this work, we show that an accurate evaluation of normalization or expectation values of PEPS is as hard to compute for typical instances as for special configurations of highest computational hardness. We discuss the structural property of average-case hardness in relation to the current research on efficient algorithms attempting tensor network contraction, hinting at a wealth of possible further insights into the average-case hardness of important problems in quantum many-body theory.

•Jan 1, 2020•44 citations

Random insights into the complexity of two-dimensional tensor network calculations

Sofía González-García, Shengqi Sang, Timothy H. Hsieh +4 more

Projected entangled pair states (PEPS) offer memory-efficient representations of some quantum many-body states that obey an entanglement area law and are the basis for classical simulations of ground states in two-dimensional (2d) condensed matter systems. However, rigorous results show that exactly computing observables from a 2d PEPS state is generically a computationally hard problem. Yet approximation schemes for computing properties of 2d PEPS are regularly used, and empirically seen to succeed, for a large subclass of (``not too entangled'') condensed matter ground states. Adopting the philosophy of random matrix theory, in this work, we analyze the complexity of approximately contracting a 2d random PEPS by exploiting an analytic mapping to an effective replicated statistical mechanics model that permits a controlled analysis at a large bond dimension. Through this statistical-mechanics lens, we argue that (i) although approximately sampling wave-function amplitudes of random PEPS faces a computational-complexity phase transition above a critical bond dimension, and (ii) one can generically efficiently estimate the norm and correlation functions for any finite bond dimension. These results are supported numerically for various bond-dimension regimes. It is an important open question whether the above results for random PEPS apply more generally also to PEPS representing physically relevant ground states.

arXiv:2307.11053•Physical review. B./Physical review. B•Jun 3, 2024•9 citations

Quantum state tomography for tensor networks in two dimensions

Zhen Qin, Zhihui Zhu

Recent work has shown that for one-dimensional quantum states that can be effectively approximated by matrix product operators (MPOs), a polynomial number of copies of the state suffices for reconstruction. Compared to MPOs in one dimension, projected entangled-pair states (PEPSs) and projected entangled-pair operators (PEPOs), which represent typical low-dimensional structures in two dimensions, are more prevalent as a looped tensor network. However, a formal analysis of the sample complexity required for estimating PEPS or PEPO has yet to be established. In this paper, we aim to address this gap by providing theoretical guarantees for the stable recovery of PEPS and PEPO. Our analysis primarily focuses on two quantum measurement schemes: $(i)$ informationally complete positive operator valued measures (IC-POVMs), specifically the spherical $t$-designs ($t \geq 3$), and $(ii)$ projective rank-one measurements, in particular Haar random projective measurements. We first establish stable embeddings for PEPSs (or PEPOs) to ensure that the information contained in the states can be preserved under these two measurement schemes. We then show that a constrained least-squares estimator achieves stable recovery for PEPSs (or PEPOs), with the recovery error bounded when the number of state copies scales linearly under spherical $t$-designs and polynomially under Haar-random projective measurements with respect to the number of qudits. These results provide theoretical support for the reliable use of PEPS and PEPO in practical quantum information processing.

arXiv:2509.16852•Physical Review A•Jan 21, 2026•0 citations
Two-dimensional tensor networks such as projected entangled pairs states (PEPS) are generally hard to contract. This is arguably the main reason why variational tensor network methods in two dimensions are still not as successful as in one dimension. However, this is not necessarily the case if the tensor network represents a gapped ground state of a local Hamiltonian; such states are subject to many constraints and contain much more structure. In this paper, we introduce an approach for approximating the expectation value of a local observable in ground states of local Hamiltonians that are represented by PEPS tensor networks. Instead of contracting the full tensor network, we try to estimate the expectation value using only a local patch of the tensor network around the observable. Surprisingly, we demonstrate that this is often easier to do when the system is frustrated. In such case, the spanning vectors of the local patch are subject to nontrivial constraints that can be utilized via a semidefinite program to calculate rigorous lower and upper bounds on the expectation value. We test our approach in one-dimensional systems, where we show how the expectation value can be calculated up to at least 3 or 4 digits of precision, even when the patch radius is smaller than the correlation length.
Tensor network states are for good reasons believed to capture ground states of gapped local Hamiltonians arising in the condensed matter context, states which are in turn expected to satisfy an entanglement area law. However, the computational hardness of contracting projected entangled pair states in two- and higher-dimensional systems is often seen as a significant obstacle when devising higher-dimensional variants of the density-matrix renormalization group method. In this work, we show that for those projected entangled pair states that are expected to provide good approximations of such ground states of local Hamiltonians, one can compute local expectation values in quasipolynomial time. We therefore provide a complexity-theoretic justification of why state-of-the-art numerical tools work so well in practice. We finally turn to the computation of local expectation values on quantum computers, providing a meaningful application for a small-scale quantum computer.
Projected entangled-pair states (PEPS) provide excellent variational wave functions for ground states of strongly correlated quantum systems in two dimensions. Determining the expectation value of such a PEPS wave function requires the contraction of a two-dimensional tensor network. Here, the authors show that this contraction can itself be formulated as a variational problem, allowing one to compare the accuracies of two commonly used contraction schemes. The authors find good agreement between the different schemes, demonstrating the robustness of PEPS simulations.
The approximate contraction of a tensor network of projected entangled pair states (PEPS) is a fundamental ingredient of any PEPS algorithm, required for the optimization of the tensors in ground state search or time evolution, as well as for the evaluation of expectation values. An exact contraction is in general impossible, and the choice of the approximating procedure determines the efficiency and accuracy of the algorithm. We analyze different previous proposals for this approximation, and show that they can be understood via the form of their environment, i.e. the operator that results from contracting part of the network. This provides physical insight into the limitation of various approaches, and allows us to introduce a new strategy, based on the idea of clusters, that unifies previous methods. The resulting contraction algorithm interpolates naturally between the cheapest and most imprecise and the most costly and most precise method. We benchmark the different algorithms with finite PEPS, and show how the cluster strategy can be used for both the tensor optimization and the calculation of expectation values. Additionally, we discuss its applicability to the parallelization of PEPS and to infinite systems.
An accurate calculation of the properties of quantum many-body systems is one of the most important yet intricate challenges of modern physics and computer science. In recent years, the tensor network ansatz has established itself as one of the most promising approaches enabling striking efficiency of simulating static properties of one-dimensional systems and abounding numerical applications in condensed matter theory. In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P-complete. Therefore an efficient algorithm for PEPS contraction would allow solving exceedingly difficult combinatorial counting problems, which is considered highly unlikely. Due to the importance of understanding two- and three-dimensional systems the question currently remains: Are the known constructions typical of states relevant for quantum many-body systems? In this work, we show that an accurate evaluation of normalization or expectation values of PEPS is as hard to compute for typical instances as for special configurations of highest computational hardness. We discuss the structural property of average-case hardness in relation to the current research on efficient algorithms attempting tensor network contraction, hinting at a wealth of possible further insights into the average-case hardness of important problems in quantum many-body theory.
Projected entangled pair states (PEPS) offer memory-efficient representations of some quantum many-body states that obey an entanglement area law and are the basis for classical simulations of ground states in two-dimensional (2d) condensed matter systems. However, rigorous results show that exactly computing observables from a 2d PEPS state is generically a computationally hard problem. Yet approximation schemes for computing properties of 2d PEPS are regularly used, and empirically seen to succeed, for a large subclass of (``not too entangled'') condensed matter ground states. Adopting the philosophy of random matrix theory, in this work, we analyze the complexity of approximately contracting a 2d random PEPS by exploiting an analytic mapping to an effective replicated statistical mechanics model that permits a controlled analysis at a large bond dimension. Through this statistical-mechanics lens, we argue that (i) although approximately sampling wave-function amplitudes of random PEPS faces a computational-complexity phase transition above a critical bond dimension, and (ii) one can generically efficiently estimate the norm and correlation functions for any finite bond dimension. These results are supported numerically for various bond-dimension regimes. It is an important open question whether the above results for random PEPS apply more generally also to PEPS representing physically relevant ground states.
Recent work has shown that for one-dimensional quantum states that can be effectively approximated by matrix product operators (MPOs), a polynomial number of copies of the state suffices for reconstruction. Compared to MPOs in one dimension, projected entangled-pair states (PEPSs) and projected entangled-pair operators (PEPOs), which represent typical low-dimensional structures in two dimensions, are more prevalent as a looped tensor network. However, a formal analysis of the sample complexity required for estimating PEPS or PEPO has yet to be established. In this paper, we aim to address this gap by providing theoretical guarantees for the stable recovery of PEPS and PEPO. Our analysis primarily focuses on two quantum measurement schemes: (i)(i)(i) informationally complete positive operator valued measures (IC-POVMs), specifically the spherical ttt-designs (t≥3t \geq 3t≥3), and (ii)(ii)(ii) projective rank-one measurements, in particular Haar random projective measurements. We first establish stable embeddings for PEPSs (or PEPOs) to ensure that the information contained in the states can be preserved under these two measurement schemes. We then show that a constrained least-squares estimator achieves stable recovery for PEPSs (or PEPOs), with the recovery error bounded when the number of state copies scales linearly under spherical ttt-designs and polynomially under Haar-random projective measurements with respect to the number of qudits. These results provide theoretical support for the reliable use of PEPS and PEPO in practical quantum information processing.