dorsal/arxiv
View SchemaThe 2-local Hamiltonian problem encompasses NP
| Authors | Pawel Wocjan, Thomas Beth |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0301087 |
| URL | https://arxiv.org/abs/quant-ph/0301087 |
Abstract
We show that the NP complete problems MAX CUT and INDEPENDENT SET can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. He introduced the quantum complexity class BQNP as the quantum analog of NP, and showed that the 5-local Hamiltonian problem is BQNP-complete. It is not known whether the s-local Hamiltonian problem is BQNP-complete for s smaller than 5. Therefore it is interesting to determine what problems can be reduced to the s-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulated as a 3-local Hamiltonian problem. We extend his result by showing that 2-locality is sufficient in order to encompass NP.
{
"annotation_id": "0a0d44be-b6c0-4d9a-a9be-8eb9ca901550",
"date_created": "2026-03-02T18:01:55.999000Z",
"date_modified": "2026-03-02T18:01:55.999000Z",
"file_hash": "8c2727d0cbbf42bb6bb1a3747fc998e242df6c9e06014c60688a83978e83525f",
"private": false,
"record": {
"abstract": "We show that the NP complete problems MAX CUT and INDEPENDENT SET can be\nformulated as the 2-local Hamiltonian problem as defined by Kitaev. He\nintroduced the quantum complexity class BQNP as the quantum analog of NP, and\nshowed that the 5-local Hamiltonian problem is BQNP-complete. It is not known\nwhether the s-local Hamiltonian problem is BQNP-complete for s smaller than 5.\nTherefore it is interesting to determine what problems can be reduced to the\ns-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulated as a\n3-local Hamiltonian problem. We extend his result by showing that 2-locality is\nsufficient in order to encompass NP.",
"arxiv_id": "quant-ph/0301087",
"authors": [
"Pawel Wocjan",
"Thomas Beth"
],
"categories": [
"quant-ph"
],
"title": "The 2-local Hamiltonian problem encompasses NP",
"url": "https://arxiv.org/abs/quant-ph/0301087"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "16a3d7ed-487e-447f-a800-9cfe53671939",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}