  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
