QMA-complete problems for stoquastic Hamiltonians and Markov matrices

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.