Coauthors: Stephen Jordan

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.