{
  "annotation_id": "f6725c6e-bd75-4aa3-8d41-6c9b6f66c872",
  "date_created": "2026-03-02T18:02:10.438000Z",
  "date_modified": "2026-03-02T18:02:10.438000Z",
  "file_hash": "a607b55ce86056409f59985e6af11ddb2ad18d1ccf8b148401acbe48b5c2cc10",
  "private": false,
  "record": {
    "abstract": "This paper shows that, if we could examine the entire history of a hidden\nvariable, then we could efficiently solve problems that are believed to be\nintractable even for quantum computers. In particular, under any\nhidden-variable theory satisfying a reasonable axiom called \"indifference to\nthe identity,\" we could solve the Graph Isomorphism and Approximate Shortest\nVector problems in polynomial time, as well as an oracle problem that is known\nto require quantum exponential time. We could also search an N-item database\nusing O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover\u0027s search\nalgorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we\ncould probably not solve NP-complete problems in polynomial time. We thus\nobtain the first good example of a model of computation that appears slightly\nmore powerful than the quantum computing model.",
    "arxiv_id": "quant-ph/0408119",
    "authors": [
      "Scott Aaronson"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Computing and Hidden Variables II: The Complexity of Sampling   Histories",
    "url": "https://arxiv.org/abs/quant-ph/0408119"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "bcfd246e-49ed-4112-8997-e4a2d1835fc7",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}