Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems
Author:
- 20 September 2007
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 76 (3) , 030307
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 Hamiltonians with a fixed local dimension and -body local terms, or local dimension and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes “bounded error, quantum polynomial time”). 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 density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction—i.e., a generalization of the Bose-Hubbard model.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Computational Complexity of Projected Entangled Pair StatesPhysical Review Letters, 2007
- Quantum Computational Complexity of the-Representability Problem: QMA CompletePhysical Review Letters, 2007
- Computational Difficulty of Global Variations in the Density Matrix Renormalization GroupPhysical Review Letters, 2006
- Matrix product states represent ground states faithfullyPhysical Review B, 2006
- Solving gapped Hamiltonians locallyPhysical Review B, 2006
- Reversible universal quantum computation within translation-invariant systemsPhysical Review A, 2006
- Perfect transfer of arbitrary states in quantum spin networksPhysical Review A, 2005
- Density Matrix Renormalization Group and Periodic Boundary Conditions: A Quantum Information PerspectivePhysical Review Letters, 2004
- Quantum Communication through an Unmodulated Spin ChainPhysical Review Letters, 2003
- Density matrix formulation for quantum renormalization groupsPhysical Review Letters, 1992