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:1606.06301 · Physical Review A

Approximating local observables on projected entangled pair states

M. Schwarz, Oliver Buerschaper, Jens Eisert

Published Jun 20, 2017• 21 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.95.060102

Related papers

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

Anurag Anshu, Itai Arad, Aditya Jain

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.

arXiv:1603.06049•Physical review. B./Physical review. B•Nov 28, 2016•9 citations

Computational complexity of injective projected entangled pair states

Dylan Harley, Freek Witteveen, Daniel Malz

Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.

arXiv:2509.19963•Sep 24, 2025•6 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•13 citations

Implementing global Abelian symmetries in projected entangled-pair state algorithms

Bela Bauer, Philippe Corboz, Román Orús +1 more

Due to the unfavorable scaling of tensor-network methods with the refinement parameter $M$, new approaches are necessary to improve the efficiency of numerical simulations based on such states, in particular for gapless, strongly entangled systems. In one-dimensional density matrix renormalization group methods, the use of Abelian symmetries has led to large computational gain. In higher-dimensional tensor networks, this is associated with significant technical efforts and additional approximations. We explain a formalism to implement such symmetries in two-dimensional tensor-network states and present benchmark results that confirm the validity of these approximations in the context of projected entangled-pair state algorithms.

arXiv:1010.3595•Physical Review B•Mar 18, 2011•129 citations

Computational Complexity of Projected Entangled Pair States

Norbert Schuch, Michael M. Wolf, Frank Verstraete +1 more

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.

arXiv:quant-ph/0611050•Physical Review Letters•Apr 4, 2007•346 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•31 citations
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.
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.
Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.
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.
Due to the unfavorable scaling of tensor-network methods with the refinement parameter MMM, new approaches are necessary to improve the efficiency of numerical simulations based on such states, in particular for gapless, strongly entangled systems. In one-dimensional density matrix renormalization group methods, the use of Abelian symmetries has led to large computational gain. In higher-dimensional tensor networks, this is associated with significant technical efforts and additional approximations. We explain a formalism to implement such symmetries in two-dimensional tensor-network states and present benchmark results that confirm the validity of these approximations in the context of projected entangled-pair state algorithms.
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.
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.