@article {1396, title = {QMA-complete problems for stoquastic Hamiltonians and Markov matrices}, journal = {Physical Review A}, volume = {81}, year = {2010}, month = {2010/3/29}, 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 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. }, doi = {10.1103/PhysRevA.81.032331}, url = {http://arxiv.org/abs/0905.4755v2}, author = {Stephen P. Jordan and David Gosset and Peter J. Love} }