A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems

Abstract

Here we present a problem related to the local Hamiltonian problem (identifying whether the ground state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for problems with a fixed local dimension and O(\log(N))-body local terms, or local dimension N and 2-body terms, there are instances of the problem which are QMA-complete. We discuss the implications for the computational complexity of finding ground states of these systems, and hence for any classical approximation techniques that one could apply including DMRG, Matrix Product States and MERA. One important example is a 1D lattice of bosons with nearest-neighbor hopping at constant filling fraction i.e. a generalization of the Bose-Hubbard model.

4 pages. v2: Significantly revised interpretation of results. v3: updated references, added example class of Hamiltonians

References in corpus (7)

• Matrix product states represent ground states faithfully
• DMRG and periodic boundary conditions: a quantum information perspective
• Criticality, the area law, and the computational power of PEPS
• Perfect Transfer of Arbitrary States in Quantum Spin Networks
• The computational complexity of PEPS
• N-representability is QMA-complete
• Computational Difficulty of Global Variations in the Density Matrix Renormalization Group

Cited by in corpus (13)

• Entropy scaling and simulability by Matrix Product States
• Hamiltonian complexity
• Quantum Hamiltonian Complexity
• On entropy growth and the hardness of simulating time evolution
• The computational difficulty of finding MPS ground states
• Interacting boson problems are QMA-hard
• The Computational Power of Symmetric Hamiltonians
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• The Role of Rotational Invariance in the Properties of Hamiltonians
• Approximation, Proof Systems, and Correlations in a Quantum World