Title: Stoquastic MA and The Local Hamiltonian Problem
Speaker: Arvid Bessen, Columbia University
Date: Wednesday, February 14, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We study the local Hamiltonian problem for stoquastic Hamiltonians. In the local Hamiltonian problem we have to decide whether a Hermitian matrix that is the sum of local Hermitian matrices has a lowest eigenvalue less than a certain threshold or not. We consider the restriction of this problem to stoquastic (stochastic quantum) Hamiltonians, i.e, matrices that are the sum of local matrices which have real and non-positive off-diagonal matrix elements in the computational basis. In quantum Monte Carlo simulations stoquastic Hamiltonians are exactly those that avoid the so-called "sign problem". It is known that the general local Hamiltonian problem is QMA-complete and we will prove that the stoquastic local Hamiltonian problem is StoqMA-complete. Here StoqMA is a new complexity class we define by only allowing classical probabilistic computation, a quantum "witness", and one nonclassical measurement. Finally we prove that MA is contained in StoqMA and that StoqMA is contained in SBP and therefore also in AM and the polynomial hierarchy.
(Joint work with Sergey Bravyi, Barbara M. Terhal)