Computational difficulty of finding matrix product ground states

Norbert Schuch, J. Ignacio Cirac, Frank Verstraete

Publications: Contribution to journalArticlePeer Reviewed


We determine the computational difficulty of finding ground states of one-dimensional (1D) Hamiltonians, which are known to be matrix product states (MPS). To this end, we construct a class of 1D frustration-free Hamiltonians with unique MPS ground states and a polynomial gap above, for which finding the ground state is at least as hard as factoring. Without the uniqueness of the ground state, the problem becomes NP complete, and thus for these Hamiltonians it cannot even be certified that the ground state has been found. This poses new bounds on convergence proofs for variational methods that use MPS.
Original languageEnglish
Article number250501
Number of pages4
JournalPhysical Review Letters
Issue number25
Publication statusPublished - 27 Jun 2008

Austrian Fields of Science 2012

  • 103025 Quantum mechanics


Dive into the research topics of 'Computational difficulty of finding matrix product ground states'. Together they form a unique fingerprint.

Cite this