Matrix product operators and states: NP-hardness and undecidability

Understand

Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics.

• This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems.
• It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues.
• We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard in the system size.