{
  "annotation_id": "6d657ec7-cdbf-48ea-8ebb-c00f14109bf0",
  "date_created": "2026-03-02T18:02:09.063000Z",
  "date_modified": "2026-03-02T18:02:09.063000Z",
  "file_hash": "22a11603aa0bfdd264d008ef58e2a97252fdfc846f5ca5c50919da279771dc26",
  "private": false,
  "record": {
    "abstract": "The k-local Hamiltonian problem is a natural complete problem for the\ncomplexity class QMA, the quantum analog of NP. It is similar in spirit to\nMAX-k-SAT, which is NP-complete for k\u003c=2. It was known that the problem is\nQMA-complete for any k \u003c= 3. On the other hand 1-local Hamiltonian is in P, and\nhence not believed to be QMA-complete. The complexity of the 2-local\nHamiltonian problem has long been outstanding. Here we settle the question and\nshow that it is QMA-complete. We provide two independent proofs; our first\nproof uses only elementary linear algebra. Our second proof uses a powerful\ntechnique for analyzing the sum of two Hamiltonians; this technique is based on\nperturbation theory and we believe that it might prove useful elsewhere. Using\nour techniques we also show that adiabatic computation with two-local\ninteractions on qubits is equivalent to standard quantum computation.",
    "arxiv_id": "quant-ph/0406180",
    "authors": [
      "Julia Kempe",
      "Alexei Kitaev",
      "Oded Regev"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "journal_ref": "SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006),\n  conference version in Proc. 24th FSTTCS, p. 372-383 (2004)",
    "title": "The Complexity of the Local Hamiltonian Problem",
    "url": "https://arxiv.org/abs/quant-ph/0406180"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "cdfd37ca-a89a-468c-9978-0d6f6efc84a0",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}