dorsal/arxiv
View SchemaThe Complexity of Stoquastic Local Hamiltonian Problems
| Authors | Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, Barbara M. Terhal |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606140 |
| URL | https://arxiv.org/abs/quant-ph/0606140 |
| Journal | Quant. Inf. Comp. Vol.8, No.5, pp. 0361-0385 (2008) |
Abstract
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.
{
"annotation_id": "f38e3dad-1ab1-453c-b526-bc2105f18770",
"date_created": "2026-03-02T18:02:27.611000Z",
"date_modified": "2026-03-02T18:02:27.611000Z",
"file_hash": "705190cb2e15c3232ab6e6ca99aacdc4c50d729cede8cf066ccde8cde2ff9b9f",
"private": false,
"record": {
"abstract": "We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN)\nin the special case when a Hamiltonian obeys conditions of the Perron-Frobenius\ntheorem: all off-diagonal matrix elements in the standard basis are real and\nnon-positive. We will call such Hamiltonians, which are common in the natural\nworld, stoquastic. An equivalent characterization of stoquastic Hamiltonians is\nthat they have an entry-wise non-negative Gibbs density matrix for any\ntemperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the\ncomplexity class AM -- a probabilistic version of NP with two rounds of\ncommunication between the prover and the verifier. We also show that 2-local\nstoquastic LH-MIN is hard for the class MA. With the additional promise of\nhaving a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the\nclass POSTBPP=BPPpath -- a generalization of BPP in which a post-selective\nreadout is allowed. This last result also shows that any problem solved by\nadiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP.",
"arxiv_id": "quant-ph/0606140",
"authors": [
"Sergey Bravyi",
"David P. DiVincenzo",
"Roberto I. Oliveira",
"Barbara M. Terhal"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quant. Inf. Comp. Vol.8, No.5, pp. 0361-0385 (2008)",
"title": "The Complexity of Stoquastic Local Hamiltonian Problems",
"url": "https://arxiv.org/abs/quant-ph/0606140"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d35f60f7-8502-4c41-960f-928e9f9769d7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}