{
  "annotation_id": "af8cabeb-310b-4cb6-aa87-ea1f2fc19c1d",
  "date_created": "2026-03-02T18:02:44.530000Z",
  "date_modified": "2026-03-02T18:02:44.530000Z",
  "file_hash": "6a6d494e60a797027345f6ade18b3eca29d9ef2210fd09cd675a746ebab6bcd5",
  "private": false,
  "record": {
    "abstract": "We show that any quantum algorithm searching an ordered list of n elements\nneeds to examine at least 1/12 log n-O(1) of them. Classically, log n queries\nare both necessary and sufficient. This shows that quantum algorithms can\nachieve only a constant speedup for this problem. Our result improves lower\nbounds of Buhrman and de Wolf(quant-ph/9811046) and Farhi, Goldstone, Gutmann\nand Sipser (quant-ph/9812057).",
    "arxiv_id": "quant-ph/9902053",
    "authors": [
      "Andris Ambainis"
    ],
    "categories": [
      "quant-ph",
      "cs.CC",
      "cs.DS"
    ],
    "title": "A better lower bound for quantum algorithms searching an ordered list",
    "url": "https://arxiv.org/abs/quant-ph/9902053"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "6bf82a40-ae3d-48b1-bf81-c1cc3633d283",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}