{
  "annotation_id": "8ce8b88e-8595-4727-bf24-2af74e74c763",
  "date_created": "2026-03-02T18:01:41.634000Z",
  "date_modified": "2026-03-02T18:01:41.634000Z",
  "file_hash": "b4bb3b7dd1e7f3eeca60497d53468d1fdb1a27f769fba3afa58e17f97d7b0f9a",
  "private": false,
  "record": {
    "abstract": "We consider the quantum complexities of the following three problems:\nsearching an ordered list, sorting an un-ordered list, and deciding whether the\nnumbers in a list are all distinct. Letting N be the number of elements in the\ninput list, we prove a lower bound of \\frac{1}{\\pi}(\\ln(N)-1) accesses to the\nlist elements for ordered searching, a lower bound of \\Omega(N\\log{N}) binary\ncomparisons for sorting, and a lower bound of \\Omega(\\sqrt{N}\\log{N}) binary\ncomparisons for element distinctness. The previously best known lower bounds\nare {1/12}\\log_2(N) - O(1) due to Ambainis, \\Omega(N), and \\Omega(\\sqrt{N}),\nrespectively. Our proofs are based on a weighted all-pairs inner product\nargument.\n  In addition to our lower bound results, we give a quantum algorithm for\nordered searching using roughly 0.631 \\log_2(N) oracle accesses. Our algorithm\nuses a quantum routine for traversing through a binary search tree faster than\nclassically, and it is of a nature very different from a faster algorithm due\nto Farhi, Goldstone, Gutmann, and Sipser.",
    "arxiv_id": "quant-ph/0102078",
    "authors": [
      "Peter Hoyer",
      "Jan Neerbek",
      "Yaoyun Shi"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1007/3-540-48224-5_29",
    "journal_ref": "28th ICALP, LNCS 2076, pp. 346-357, July 2001",
    "title": "Quantum complexities of ordered searching, sorting, and element   distinctness",
    "url": "https://arxiv.org/abs/quant-ph/0102078"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "73bbcd88-97b5-4d72-b4bf-cf1ea62b1d35",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}