{
  "annotation_id": "5d70067f-aa2b-4a0b-8688-663d7559c49a",
  "date_created": "2026-03-02T18:01:49.337000Z",
  "date_modified": "2026-03-02T18:01:49.337000Z",
  "file_hash": "eddfeb33527dcc5d978ba5792f5e6af5930975ad1830c991b332f79a1dc77026",
  "private": false,
  "record": {
    "abstract": "For any quantum algorithm operating on pure states we prove that the presence\nof multi-partite entanglement, with a number of parties that increases\nunboundedly with input size, is necessary if the quantum algorithm is to offer\nan exponential speed-up over classical computation. Furthermore we prove that\nthe algorithm can be classically efficiently simulated to within a prescribed\ntolerance \\eta even if a suitably small amount of global entanglement\n(depending on \\eta) is present. We explicitly identify the occurrence of\nincreasing multi-partite entanglement in Shor\u0027s algorithm. Our results do not\napply to quantum algorithms operating on mixed states in general and we discuss\nthe suggestion that an exponential computational speed-up might be possible\nwith mixed states in the total absence of entanglement. Finally, despite the\nessential role of entanglement for pure state algorithms, we argue that it is\nnevertheless misleading to view entanglement as a key resource for quantum\ncomputational power.",
    "arxiv_id": "quant-ph/0201143",
    "authors": [
      "Richard Jozsa",
      "Noah Linden"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1098/rspa.2002.1097",
    "title": "On the role of entanglement in quantum computational speed-up",
    "url": "https://arxiv.org/abs/quant-ph/0201143"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "4e2d5345-b723-4d13-af00-235fad598568",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}