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

Contracting projected entangled pair states is average-case hard

Jonas Haferkamp, Dominik Hangleiter, Jens Eisert, Marek Gluza

Published Jan 1, 2020• 44 citations
Publisher

Abstract

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.

DOI
10.17169/refubium-30079

Related papers

Contracting projected entangled pair states is average-case hard

Jonas Haferkamp, Dominik Hangleiter, Jens Eisert +1 more

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.

arXiv:1810.00738•Physical Review Research•Jan 3, 2020•54 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

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

Sign Problem in Tensor-Network Contraction

Jielun Chen, Jiaqing Jiang, Dominik Hangleiter +1 more

We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries. Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower computational complexity as compared to tensor networks with general real or complex entries. This raises the question of how this transition in computational complexity manifests itself in the hardness of different tensor-network-contraction schemes. We pursue this question by studying random tensor networks with varying bias toward positive entries. First, we consider contraction via Monte Carlo sampling and find that the transition from hard to easy occurs when the tensor entries become predominantly positive; this can be understood as a tensor-network manifestation of the well-known negative-sign problem in quantum Monte Carlo. Second, we analyze the commonly used contraction based on boundary tensor networks. The performance of this scheme is governed by the number of correlations in contiguous parts of the tensor network (which by analogy can be thought of as entanglement). Remarkably, we find that the transition from hard to easy—i.e., from a volume-law to a boundary-law scaling of entanglement—already occurs for a slight bias of the tensor entries toward a positive mean, scaling inversely with the bond dimension D , and thus the problem becomes easy the earlier the larger D occurs. This is in contrast both to expectations and to the behavior found in Monte Carlo contraction, where the hardness at fixed bias increases with the bond dimension. To provide insight into this early breakdown of computational hardness and the accompanying entanglement transition, we construct an effective classical statistical-mechanical model that predicts a transition at a bias of the tensor entries of 1 / D , confirming our observations. We conclude by investigating the computational difficulty of computing expectation values of tensor-network wave functions (projected entangled-pair states, PEPSs) and find that in this setting, the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation that maps PEPS expectation values to a positive-valued tensor network. This not only provides insight into the origin of the observed boundary-law entanglement scaling but also suggests new approaches toward PEPS contraction based on positive decompositions.

arXiv:2404.19023•PRX Quantum•Jan 17, 2025•10 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•10 citations

Algorithms for finite projected entangled pair states

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

Projected entangled pair states (PEPS) are a promising ansatz for the study of strongly correlated quantum many-body systems in two dimensions. However, due to their high computational cost, developing and improving PEPS algorithms is necessary to make the ansatz widely usable in practice. Here we analyze several algorithmic aspects of the method. On the one hand, we quantify the connection between the correlation length of the PEPS and the accuracy of its approximate contraction and discuss how purifications can be used in the latter. On the other hand, we present algorithmic improvements for the update of the tensor that introduce drastic gains in the numerical conditioning and the efficiency of the algorithms. Finally, the state-of-the-art general PEPS code is benchmarked with the Heisenberg and quantum Ising models on lattices of up to $21\ifmmode\times\else\texttimes\fi{}21$ sites.

arXiv:1405.3259•Physical Review B•Aug 25, 2014•205 citations
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.
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.
We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries. Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower computational complexity as compared to tensor networks with general real or complex entries. This raises the question of how this transition in computational complexity manifests itself in the hardness of different tensor-network-contraction schemes. We pursue this question by studying random tensor networks with varying bias toward positive entries. First, we consider contraction via Monte Carlo sampling and find that the transition from hard to easy occurs when the tensor entries become predominantly positive; this can be understood as a tensor-network manifestation of the well-known negative-sign problem in quantum Monte Carlo. Second, we analyze the commonly used contraction based on boundary tensor networks. The performance of this scheme is governed by the number of correlations in contiguous parts of the tensor network (which by analogy can be thought of as entanglement). Remarkably, we find that the transition from hard to easy—i.e., from a volume-law to a boundary-law scaling of entanglement—already occurs for a slight bias of the tensor entries toward a positive mean, scaling inversely with the bond dimension D , and thus the problem becomes easy the earlier the larger D occurs. This is in contrast both to expectations and to the behavior found in Monte Carlo contraction, where the hardness at fixed bias increases with the bond dimension. To provide insight into this early breakdown of computational hardness and the accompanying entanglement transition, we construct an effective classical statistical-mechanical model that predicts a transition at a bias of the tensor entries of 1 / D , confirming our observations. We conclude by investigating the computational difficulty of computing expectation values of tensor-network wave functions (projected entangled-pair states, PEPSs) and find that in this setting, the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation that maps PEPS expectation values to a positive-valued tensor network. This not only provides insight into the origin of the observed boundary-law entanglement scaling but also suggests new approaches toward PEPS contraction based on positive decompositions.
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) are a promising ansatz for the study of strongly correlated quantum many-body systems in two dimensions. However, due to their high computational cost, developing and improving PEPS algorithms is necessary to make the ansatz widely usable in practice. Here we analyze several algorithmic aspects of the method. On the one hand, we quantify the connection between the correlation length of the PEPS and the accuracy of its approximate contraction and discuss how purifications can be used in the latter. On the other hand, we present algorithmic improvements for the update of the tensor that introduce drastic gains in the numerical conditioning and the efficiency of the algorithms. Finally, the state-of-the-art general PEPS code is benchmarked with the Heisenberg and quantum Ising models on lattices of up to $21\ifmmode\times\else\texttimes\fi{}21$ sites.