Computational Difficulty of Finding Matrix Product Ground States
Open Access
- 27 June 2008
- journal article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 100 (25), 250501
- https://doi.org/10.1103/physrevlett.100.250501
Abstract
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.Comment: 5 pages. v2: accepted version, Journal-Ref addeKeywords
Other Versions
This publication has 7 references indexed in Scilit:
- Quantum Simulators, Continuous-Time Automata, and Translationally Invariant SystemsPhysical Review Letters, 2008
- Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systemsPhysical Review A, 2007
- An area law for one-dimensional quantum systemsJournal of Statistical Mechanics: Theory and Experiment, 2007
- Computational Difficulty of Global Variations in the Density Matrix Renormalization GroupPhysical Review Letters, 2006
- The density-matrix renormalization groupReviews of Modern Physics, 2005
- Density Matrix Renormalization Group and Periodic Boundary Conditions: A Quantum Information PerspectivePhysical Review Letters, 2004
- Density matrix formulation for quantum renormalization groupsPhysical Review Letters, 1992