Computational difficulty of finding matrix product ground states

Autor(en)

Norbert Schuch, J. Ignacio Cirac, Frank Verstraete

Abstrakt

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.

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Externe Organisation(en)

Max-Planck-Institut für Quantenoptik

Journal

Physical Review Letters

Band

100

Anzahl der Seiten

4

ISSN

0031-9007

DOI

https://doi.org/10.1103/PhysRevLett.100.250501

Publikationsdatum

06-2008

Peer-reviewed

Ja

ÖFOS 2012

103025 Quantenmechanik

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/602d0afe-047d-4a9a-9191-6f4578c40a05