Matrix-Product Operators and States: NP-Hardness and Undecidability

M. Kliesch, D. Gross, and J. Eisert
Phys. Rev. Lett. 113, 160503 – Published 16 October 2014
PDFHTMLExport Citation

Abstract

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 (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.

  • Figure
  • Figure
  • Received 6 May 2014

DOI:https://doi.org/10.1103/PhysRevLett.113.160503

© 2014 American Physical Society

Authors & Affiliations

M. Kliesch1, D. Gross2, and J. Eisert1

  • 1QMIO Group, Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
  • 2Physikalisches Institut and Freiburg Center for Data Analysis and Modeling, Universität Freiburg, 79104 Freiburg, Germany

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 113, Iss. 16 — 17 October 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×