%0 Journal Article %J Physical Review A %D 2010 %T QMA-complete problems for stoquastic Hamiltonians and Markov matrices %A Stephen P. Jordan %A David Gosset %A Peter J. Love %X 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 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 new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems. %B Physical Review A %V 81 %8 2010/3/29 %G eng %U http://arxiv.org/abs/0905.4755v2 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.81.032331