dorsal/arxiv
View Schema3-Local Hamiltonian is QMA-complete
| Authors | Julia Kempe, Oded Regev |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0302079 |
| URL | https://arxiv.org/abs/quant-ph/0302079 |
| Journal | Quantum Computation and Information, Vol. 3(3), p. 258-64, 2003 |
Abstract
It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.
{
"annotation_id": "c42971b4-875d-408c-abe7-3c898c487399",
"date_created": "2026-03-02T18:01:56.262000Z",
"date_modified": "2026-03-02T18:01:56.262000Z",
"file_hash": "30ea22870b1adb89d14f61d77c6e072bb168fbac8a3fa927da47091eb4973906",
"private": false,
"record": {
"abstract": "It has been shown by Kitaev that the 5-local Hamiltonian problem is\nQMA-complete. Here we reduce the locality of the problem by showing that\n3-local Hamiltonian is already QMA-complete.",
"arxiv_id": "quant-ph/0302079",
"authors": [
"Julia Kempe",
"Oded Regev"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Quantum Computation and Information, Vol. 3(3), p. 258-64, 2003",
"title": "3-Local Hamiltonian is QMA-complete",
"url": "https://arxiv.org/abs/quant-ph/0302079"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "20845664-14f7-4f6c-98cf-c6cc740f0d67",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}