Eugene M. Chudnovsky, David P. Divincenzo
Physical Review B
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. © Rinton Press.
Eugene M. Chudnovsky, David P. Divincenzo
Physical Review B
Sergey Bravyi, David Gosset, et al.
STOC 2024
Srinivasan Arunachalam, Sergey Bravyi, et al.
TQC 2022
Sergey Bravyi, David Gosset, et al.
Nature Physics