%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