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:2307.11053 · Physical review. B./Physical review. B

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

Sofía González-García, Shengqi Sang, Timothy H. Hsieh, Sergio Boixo, Guifré Vidal, Andrew C. Potter, Romain Vasseur

Published Jun 3, 2024• 13 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevb.109.235102

Related papers

Gradient optimization of finite projected entangled pair states

Wen-Yuan Liu, Shaojun Dong, Yong‐Jian Han +2 more

Projected entangled pair states (PEPS) methods have been proven to be powerful tools to solve strongly correlated quantum many-body problems in two dimensions. However, due to the high computational scaling with the virtual bond dimension $D$, in a practical application, PEPS are often limited to rather small bond dimensions, which may not be large enough for some highly entangled systems, for instance, frustrated systems. Optimization of the ground state using the imaginary time evolution method with a simple update scheme may go to a larger bond dimension. However, the accuracy of the rough approximation to the environment of the local tensors is questionable. Here, we demonstrate that by combining the imaginary time evolution method with a simple update, Monte Carlo sampling techniques and gradient optimization will offer an efficient method to calculate the PEPS ground state. By taking advantage of massive parallel computing, we can study quantum systems with larger bond dimensions up to $D=10$ without resorting to any symmetry. Benchmark tests of the method on the ${J}_{1}\ensuremath{-}{J}_{2}$ model give impressive accuracy compared with exact results.

arXiv:1611.09467•Physical review. B./Physical review. B•May 24, 2017•67 citations

Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States

Frank Verstraete, M. M. Wolf, David Pérez-García +1 more

The projected entangled pair state (PEPS) representation of quantum states on two-dimensional lattices induces an entanglement based hierarchy in state space. We show that the lowest levels of this hierarchy exhibit a very rich structure including states with critical and topological properties. We prove, in particular, that coherent versions of thermal states of any local 2D classical spin model correspond to such PEPS, which are in turn ground states of local 2D quantum Hamiltonians. This correspondence maps thermal onto quantum fluctuations, and it allows us to analytically construct critical quantum models exhibiting a strict area law scaling of the entanglement entropy in the face of power law decaying correlations. Moreover, it enables us to show that there exist PEPS which can serve as computational resources for the solution of NP-hard problems.

arXiv:quant-ph/0601075•Physical Review Letters•Jun 6, 2006•603 citations

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

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

Efficient representation of minimally entangled typical thermal states in two dimensions via projected entangled pair states

Aritra Sinha, Marek M. Rams, Jacek Dziarmaga

The minimally entangled typical thermal states (METTS) are an ensemble of pure states, equivalent to the Gibbs thermal state, designed with an efficient tensor network representation in mind. In this article, we use the projected entangled pair states (PEPS) as their representation on a two-dimensional (2D) lattice. Unlike matrix product states (MPS), which for 2D systems are limited by an exponential computational barrier in the lattice size, PEPS provides a more tractable approach. To substantiate the prowess of PEPS in modeling METTS (dubbed PEPS-METTS), we benchmark it against the purification method in the context of the 2D quantum Ising model at its critical temperature. Our analysis reveals that PEPS-METTS achieves accurate results with significantly lower bond dimensions. We further corroborate this finding in the 2D Fermi-Hubbard model. At a technical level, we introduce an efficient zipper method to obtain PEPS boundary MPS needed to compute expectation values and perform sampling. The imaginary time evolution is done with the neighborhood tensor update.

arXiv:2310.08533•Physical review. B./Physical review. B•Jan 19, 2024•13 citations

Logarithmic Bond Dimension Scaling in 2D PEPS Contraction via Successive Randomized Compression

Ayad Alhusseiny

We introduce a randomized algorithm for the classical simulation of two-dimensional lattice systems via Projected Entangled Pair States (PEPS). Multiplicative bond-dimension growth during row-by-row boundary Matrix Product State (MPS) contraction poses the central computational bottleneck. The 2D Successive Randomized Compression (2D-SRC) algorithm resolves this by replacing truncated singular value decomposition (SVD) with a single-pass randomized QR projection: per-site complexity drops from $\mathcal{O}(mn^2)$ to $\mathcal{O}(mnk)$ for sketching dimension $k \ll n$. A gauge-loss deficiency unique to 2D sweeps corrupts the physical partition function weight at the final boundary site; the Boundary-Weight Preservation Scheme resolves this at zero additional computational cost. Sequential projection errors along the boundary sweep form a matrix-valued Doob martingale; applying the Matrix Freedman inequality establishes a rigorous global error bound. For gapped area-law states, the target boundary bond dimension scales only logarithmically with lattice size: $\bar{\chi} \sim (\xi/2)\log N$, where $\xi$ is the physical correlation length. Benchmarks on the 2D Transverse Field Ising Model (TFIM) reproduce the ferromagnetic-to-paramagnetic phase transition with a $2.5\times$ speedup over the deterministic SVD baseline at a relative energy error below $4\%$. At intermediate bond dimensions, the dense 2D-SRC implementation achieves a $10\times$ speed advantage over standard tensor network libraries.

•Jun 20, 2026•0 citations
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.
Projected entangled pair states (PEPS) methods have been proven to be powerful tools to solve strongly correlated quantum many-body problems in two dimensions. However, due to the high computational scaling with the virtual bond dimension DDD, in a practical application, PEPS are often limited to rather small bond dimensions, which may not be large enough for some highly entangled systems, for instance, frustrated systems. Optimization of the ground state using the imaginary time evolution method with a simple update scheme may go to a larger bond dimension. However, the accuracy of the rough approximation to the environment of the local tensors is questionable. Here, we demonstrate that by combining the imaginary time evolution method with a simple update, Monte Carlo sampling techniques and gradient optimization will offer an efficient method to calculate the PEPS ground state. By taking advantage of massive parallel computing, we can study quantum systems with larger bond dimensions up to D=10D=10D=10 without resorting to any symmetry. Benchmark tests of the method on the ${J}_{1}\ensuremath{-}{J}_{2}$ model give impressive accuracy compared with exact results.
The projected entangled pair state (PEPS) representation of quantum states on two-dimensional lattices induces an entanglement based hierarchy in state space. We show that the lowest levels of this hierarchy exhibit a very rich structure including states with critical and topological properties. We prove, in particular, that coherent versions of thermal states of any local 2D classical spin model correspond to such PEPS, which are in turn ground states of local 2D quantum Hamiltonians. This correspondence maps thermal onto quantum fluctuations, and it allows us to analytically construct critical quantum models exhibiting a strict area law scaling of the entanglement entropy in the face of power law decaying correlations. Moreover, it enables us to show that there exist PEPS which can serve as computational resources for the solution of NP-hard problems.
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.
The minimally entangled typical thermal states (METTS) are an ensemble of pure states, equivalent to the Gibbs thermal state, designed with an efficient tensor network representation in mind. In this article, we use the projected entangled pair states (PEPS) as their representation on a two-dimensional (2D) lattice. Unlike matrix product states (MPS), which for 2D systems are limited by an exponential computational barrier in the lattice size, PEPS provides a more tractable approach. To substantiate the prowess of PEPS in modeling METTS (dubbed PEPS-METTS), we benchmark it against the purification method in the context of the 2D quantum Ising model at its critical temperature. Our analysis reveals that PEPS-METTS achieves accurate results with significantly lower bond dimensions. We further corroborate this finding in the 2D Fermi-Hubbard model. At a technical level, we introduce an efficient zipper method to obtain PEPS boundary MPS needed to compute expectation values and perform sampling. The imaginary time evolution is done with the neighborhood tensor update.
We introduce a randomized algorithm for the classical simulation of two-dimensional lattice systems via Projected Entangled Pair States (PEPS). Multiplicative bond-dimension growth during row-by-row boundary Matrix Product State (MPS) contraction poses the central computational bottleneck. The 2D Successive Randomized Compression (2D-SRC) algorithm resolves this by replacing truncated singular value decomposition (SVD) with a single-pass randomized QR projection: per-site complexity drops from O(mn2)\mathcal{O}(mn^2)O(mn2) to O(mnk)\mathcal{O}(mnk)O(mnk) for sketching dimension k≪nk \ll nk≪n. A gauge-loss deficiency unique to 2D sweeps corrupts the physical partition function weight at the final boundary site; the Boundary-Weight Preservation Scheme resolves this at zero additional computational cost. Sequential projection errors along the boundary sweep form a matrix-valued Doob martingale; applying the Matrix Freedman inequality establishes a rigorous global error bound. For gapped area-law states, the target boundary bond dimension scales only logarithmically with lattice size: χˉ∼(ξ/2)log⁡N\bar{\chi} \sim (\xi/2)\log Nχˉ​∼(ξ/2)logN, where ξ\xiξ is the physical correlation length. Benchmarks on the 2D Transverse Field Ising Model (TFIM) reproduce the ferromagnetic-to-paramagnetic phase transition with a 2.5×2.5\times2.5× speedup over the deterministic SVD baseline at a relative energy error below 4%4\%4%. At intermediate bond dimensions, the dense 2D-SRC implementation achieves a 10×10\times10× speed advantage over standard tensor network libraries.