The complexity of stoquastic local Hamiltonian problems (pp0361-0385)
          Sergey Bravyi, David P. DiVincenzo, Roberto Oliveira, and Barbara M. Terhal
          doi: https://doi.org/10.26421/QIC8.5-1
Abstracts: We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM — a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class PostBPP=BPPpath— a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians is in PostBPP.
Key words: PostBPP, complexity