  Matrix Product States (MPS) and Projected Entangled Pair States (PEPS) are
powerful analytical and numerical tools to assess quantum many-body systems in
one and higher dimensions, respectively. While MPS are comprehensively
understood, in PEPS fundamental questions, relevant analytically as well as
numerically, remain open, such as how to encode symmetries in full generality,
or how to stabilize numerical methods using canonical forms. Here, we show that
these key problems, as well as a number of related questions, are
algorithmically undecidable, that is, they cannot be fully resolved in a
systematic way. Our work thereby exposes fundamental limitations to a full and
unbiased understanding of quantum many-body systems using PEPS.
