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:quant-ph/0611050 · Physical Review Letters

Computational Complexity of Projected Entangled Pair States

Norbert Schuch, Michael M. Wolf, Frank Verstraete, J. I. Cirac

Published Apr 4, 2007• 346 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.98.140506

Related papers

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

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•131 citations

Preparing Projected Entangled Pair States on a Quantum Computer

Martin Schwarz, Kristan Temme, Frank Verstraete

We present a quantum algorithm to prepare injective projected entangled pair states (PEPS) on a quantum computer, a class of open tensor networks representing quantum states. The run time of our algorithm scales polynomially with the inverse of the minimum condition number of the PEPS projectors and, essentially, with the inverse of the spectral gap of the PEPS's parent Hamiltonian.

arXiv:1104.1410•Physical Review Letters•Mar 13, 2012•59 citations

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•21 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

Studies of Infinite Two-Dimensional Quantum Lattice Systems with Projected Entangled Pair States

Jacob Jordan

Determining the properties of quantum many-body systems is a central challenge in modern physics. Being able to determine the macroscopic properties of a system from its microscopic description would hasten progress in many fields of science and technology. However, we currently lack the tools to solve such problems generally, or even to develop a theoretical intuition about how many systems might behave. From a simple Hamiltonian description of the system, one may obtain complex, highly correlated collective behaviour. Computational techniques have played a major part in the effort to determine properties of quantum many-body systems. However, as the total degrees of freedom in the system scales exponentially in the system size, numerical diagonalization of the Hamiltonian quickly becomes computationally intractable and one must develop more efficient approximate techniques to explore the system. Present numerical methods such as quantum Monte Carlo and series expansion have provided insight into many systems of interest, but are also held back by fundamental difficulties. In this thesis, we focus on tensor networks, a relatively new ansatz for representing quantum many-body states. Tensor networks are motivated by two ideas from quantum information: firstly, that quantum entanglement is the source of the immense difficulty of simulating quantum systems classically, and secondly that the ground states of certain Hamiltonians exist in a low-entanglement region of the entire Hilbert space. The strength of tensor networks is that they provide a systematic way of representing this class of low-entanglement quantum states. In particular, this thesis describes the iPEPS algorithm for computing the ground states of infinite, two-dimensional quantum lattice systems based on the Projected Entangled Pair States (PEPS) ansatz. We then benchmark the algorithm by computing the phase diagrams of several systems that have been studied with other techniques. Lastly, we apply our algorithm to problems that are not well solved by current approaches, such as frustrated spin systems.

•Jan 1, 2011•7 citations
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) 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.
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.
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) 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.
Determining the properties of quantum many-body systems is a central challenge in modern physics. Being able to determine the macroscopic properties of a system from its microscopic description would hasten progress in many fields of science and technology. However, we currently lack the tools to solve such problems generally, or even to develop a theoretical intuition about how many systems might behave. From a simple Hamiltonian description of the system, one may obtain complex, highly correlated collective behaviour. Computational techniques have played a major part in the effort to determine properties of quantum many-body systems. However, as the total degrees of freedom in the system scales exponentially in the system size, numerical diagonalization of the Hamiltonian quickly becomes computationally intractable and one must develop more efficient approximate techniques to explore the system. Present numerical methods such as quantum Monte Carlo and series expansion have provided insight into many systems of interest, but are also held back by fundamental difficulties. In this thesis, we focus on tensor networks, a relatively new ansatz for representing quantum many-body states. Tensor networks are motivated by two ideas from quantum information: firstly, that quantum entanglement is the source of the immense difficulty of simulating quantum systems classically, and secondly that the ground states of certain Hamiltonians exist in a low-entanglement region of the entire Hilbert space. The strength of tensor networks is that they provide a systematic way of representing this class of low-entanglement quantum states. In particular, this thesis describes the iPEPS algorithm for computing the ground states of infinite, two-dimensional quantum lattice systems based on the Projected Entangled Pair States (PEPS) ansatz. We then benchmark the algorithm by computing the phase diagrams of several systems that have been studied with other techniques. Lastly, we apply our algorithm to problems that are not well solved by current approaches, such as frustrated spin systems.