Criticality, the area law, and the computational power of projected entangled pair states

The projected entangled pair state (PEPS) representation of quantum states on two-dimensional lattices induces an entanglement based hierarchy in state space. We show that the lowest levels of this hierarchy exhibit a very rich structure including states with critical and topological properties. We prove, in particular, that coherent versions of thermal states of any local 2D classical spin model correspond to such PEPS, which are in turn ground states of local 2D quantum Hamiltonians. This correspondence maps thermal onto quantum fluctuations, and it allows us to analytically construct critical quantum models exhibiting a strict area law scaling of the entanglement entropy in the face of power law decaying correlations. Moreover, it enables us to show that there exist PEPS which can serve as computational resources for the solution of NP-hard problems.