The Complexity of Stoquastic Local Hamiltonian Problems

Simple item page
dc.creatorBravyi, Sergey
dc.creatorDiVincenzo, David P.
dc.creatorOliveira, Roberto I.
dc.creatorTerhal, Barbara M.
dc.date2006-06-16
dc.date2007-10-02
dc.date.accessioned2026-07-07T12:56:12Z
dc.date.available2026-07-07T12:56:12Z
dc.descriptionWe study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: 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 lies in PostBPP.
dc.description21 pages Latex, 1 figure. v2 contains several small corrections. v3 has more small corrections
dc.identifierhttps://arxiv.org/abs/quant-ph/0606140
dc.identifierhttp://arxiv.org/abs/quant-ph/0606140
dc.identifierQuant. Inf. Comp. Vol.8, No.5, pp. 0361-0385 (2008)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/224502
dc.subjectQuantum Physics
dc.titleThe Complexity of Stoquastic Local Hamiltonian Problems
dc.typetext

Files

Collections

arXiv