  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 renormalisation
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
quasi-polynomial time. We therefore provide a complexity-theoretic
justification of why state-of-the-art numerical tools work so well in practice.
We comment on how the transfer operators of such projected entangled pair
states have a gap and discuss notions of local topological quantum order. We
finally turn to the computation of local expectation values on quantum
computers, providing a meaningful application for a small-scale quantum
computer.
