The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
arXiv:0712.1388
Abstract
The Local Hamiltonian problem (finding the ground state energy of a quantum system) is known to be QMA-complete. The Local Consistency problem (deciding whether descriptions of small pieces of a quantum system are consistent) is also known to be QMA-complete. Here we consider special cases of Local Hamiltonian, for ``stoquastic'' and 1-dimensional systems, that seem to be strictly easier than QMA. We show that there exist analogous special cases of Local Consistency, that have equivalent complexity (up to poly-time oracle reductions). Our main technical tool is a new reduction from Local Consistency to Local Hamiltonian, using SDP duality.
18 pages, submitted to IEEE Conference on Computational Complexity (CCC). v2: slightly revised introduction
References in corpus (13)
- The density-matrix renormalization group
- Efficient simulation of one-dimensional quantum many-body systems
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- The power of quantum systems on a line
- N-representability is QMA-complete
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Quantum NP - A Survey
- A new construction for a QMA complete 3-local Hamiltonian
- Merlin-Arthur Games and Stoquastic Complexity
- Compatibility of subsystem states and convex geometry
- A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
- The Complexity of the Consistency and N-representability Problems for Quantum States
- The Complexity of Quantum Systems on a One-dimensional Chain