



01051nas a2200145   4500008004100000245007400041210006900115260001400184490000700198520060100205100002400806700001800830700002000848856003700868       2010                        eng d00aQMA-complete problems for stoquastic Hamiltonians and Markov matrices0 aQMAcomplete problems for stoquastic Hamiltonians and Markov matr  c2010/3/290 v813 a  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.
1 aJordan, Stephen, P.1 aGosset, David1 aLove, Peter, J.  uhttp://arxiv.org/abs/0905.4755v2