Journal
PHYSICAL REVIEW LETTERS
Volume 100, Issue 25, Pages -Publisher
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevLett.100.250501
Keywords
-
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available