Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices

We show that finding the lowest eigenvalue of a $3$-local symmetric stochastic matrix is Quantum-Merlin-Arthur-complete (QMA-complete). We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration-free Hamiltonian is universal. Our results give a QMA-complete problem arising in the classical setting of Markov chains and adiabatically universal Hamiltonians that arise in many physical systems. DOI: http://dx.doi.org/10.1103/PhysRevA.81.032331 © 2010 The American Physical Society