Orateur
Description
Tensor network states offer memory-efficient representations of quantum many-body states, and play a key role in classical simulations of quantum materials, chemistry, and circuits. However, rigorous results show that exactly computing observables from a tensor network state is generically a computationally hard problem outside of special instances such as 1d matrix-product states. Yet, approximation schemes for computing properties of 2d projected entangled pair states (PEPS) have been widely and successfully used without encountering any sign of exponential hardness. Adopting the philosophy of random matrix theory, in this talk I will analyze the complexity of approximately contracting a 2d 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, I will argue that: although approximating individual wave-function amplitudes of a PEPS faces a computational-complexity phase transition above a critical bond dimension, one can generically efficiently estimate physical properties, such as correlation functions, for any finite bond dimension.
