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

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 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, 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

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Tensor renormalization group approach to 2D classical lattice models
• The iTEBD algorithm beyond unitary evolution
• A tensor network study of the complete ground state phase diagram of the spin-1 bilinear-biquadratic Heisenberg model on the square lattice
• Corner transfer matrices in statistical mechanics

Cited by in corpus (5)

• Measuring the Loschmidt amplitude for finite-energy properties of the Fermi-Hubbard model on an ion-trap quantum computer
• Field theory of monitored, interacting fermion dynamics with charge conservation
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Free-Fermion Measurement-Induced Volume- to Area-Law Entanglement Transition in the Presence of Fermion Interactions
• Using matrix-product states for time-series machine learning