QMA-complete problems for stoquastic Hamiltonians and Markov matrices
Authors:
Preprint
Abstract
We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation in the highest energy state and certain other excited states of a stoquastic Hamiltonian is universal. These results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians which arise in many physical systems.Keywords
All Related Versions
- Version 1, 2009-05-28, ArXiv
- Version 2, 2010-03-29, ArXiv
- Published version: Physical Review A, 81 (3).
This publication has 7 references indexed in Scilit:
- Complexity of Stoquastic Frustration-Free HamiltoniansSIAM Journal on Computing, 2010
- The complexity of quantum spin systems on a two-dimensional square latticeQuantum Information & Computation, 2008
- Realizable Hamiltonians for universal adiabatic quantum computersPhysical Review A, 2008
- The complexity of stoquastic local Hamiltonian problemsQuantum Information & Computation, 2008
- Error-correcting codes for adiabatic quantum computationPhysical Review A, 2006
- The Complexity of the Local Hamiltonian ProblemSIAM Journal on Computing, 2006
- Robustness of adiabatic quantum computationPhysical Review A, 2001