Fetching the paper…

Reading the bibliography…

The computational difficulty of finding MPS ground states · Around

2008

The computational difficulty of finding MPS ground states

Schuch, Norbert, Cirac, Ignacio, Verstraete, Frank

Original
PDF
Post on X

Understand

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.

Built on

S. R. White, Phys. Rev. Lett. 69
1992
Earlier work this paper cites.
C. M. Papadimitriou, Computational complexity (Addison-Wesley, Reading, MA, 1994)
1994
Earlier work this paper cites.
D. Aharonov and T. Naveh (2002), eprint quant-ph/0210077
2002
Earlier work this paper cites.
A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and quantum computation (American Mathematical Society, Providence, Rhode Island, 2002)
2002
Earlier work this paper cites.

Similar

F. Verstraete, D. Porras, and J. I. Cirac, Phys. Rev. Lett. 93
2004
Cited alongside, same era.
U. Schollwöck, Rev. Mod. Phys. 77
2005
Cited alongside, same era.
J. Eisert, Phys. Rev. Lett. 97
2006
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal (2006), eprint quant-ph/0606140
2006
Cited alongside, same era.

Then

D. Aharonov, D. Gottesman, S. Irani, and J. Kempe (2007), eprint arXiv:0705.4077
Original
2007
Later among the works it cites.
A. Kay, Phys. Rev. A 76
Original
2008
Closest in time.
M. B. Hastings, J. Stat. Mech. P08024 (2007), arXiv:0705.2024
Original
2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…