The computational difficulty of finding MPS ground states

Details The computational difficulty of finding MPS ground states The computational difficulty of finding MPS ground states

2008-02-22

arxiv.org/abs/0802.3351v2

Phys. Rev. Lett. 100, 250501 (2008)

Physics

Quantum Physics

5 pages. v2: accepted version, Journal-Ref added

Scientific paper

10.1103/PhysRevLett.100.250501

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. By lifting the requirement of a unique ground state, we obtain a class for which finding the ground state solves an NP-complete problem. Therefore, for these Hamiltonians it is not even possible to certify that the ground state has been found. Our results thus imply that in order to prove convergence of variational methods over MPS, as the Density Matrix Renormalization Group, one has to put more requirements than just MPS ground states and a polynomial spectral gap.

Affiliated with

Also associated with

No associations

Rating

The computational difficulty of finding MPS ground states does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The computational difficulty of finding MPS ground states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational difficulty of finding MPS ground states will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303520