{
  "annotation_id": "2e972c8d-f9c2-4ff6-8438-d1743ccabbe9",
  "date_created": "2026-03-02T18:02:44.969000Z",
  "date_modified": "2026-03-02T18:02:44.969000Z",
  "file_hash": "c9f8900bf8fa44cc88cf658d5dec01180ea64be8de21df3e0864692accd53aee",
  "private": false,
  "record": {
    "abstract": "We consider the problem of inserting a new item into an ordered list of N-1\nitems. The length of an algorithm is measured by the number of comparisons it\nmakes between the new item and items already on the list. Classically,\ndetermining the insertion point requires log N comparisons. We show that, for N\nlarge, no quantum algorithm can reduce the number of comparisons below log N/(2\nloglog N).",
    "arxiv_id": "quant-ph/9812057",
    "authors": [
      "E. Farhi",
      "J. Goldstone",
      "S. Gutmann",
      "M. Sipser"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "A Limit on the Speed of Quantum Computation for Insertion into an   Ordered List",
    "url": "https://arxiv.org/abs/quant-ph/9812057"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "52b5dc96-b59e-4441-b298-8e5376294dfd",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}