Physics – Quantum Physics
Scientific paper
2006-06-16
Quant. Inf. Comp. Vol.8, No.5, pp. 0361-0385 (2008)
Physics
Quantum Physics
21 pages Latex, 1 figure. v2 contains several small corrections. v3 has more small corrections
Scientific paper
We 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.
Bravyi Sergey
DiVincenzo David P.
Oliveira Roberto I.
Terhal Barbara M.
No associations
LandOfFree
The Complexity of Stoquastic Local Hamiltonian Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Stoquastic Local Hamiltonian Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Stoquastic Local Hamiltonian Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-390506