{
  "annotation_id": "024f5e6c-8a7d-40ea-962e-d5bfe6205a9e",
  "date_created": "2026-03-02T18:01:38.858000Z",
  "date_modified": "2026-03-02T18:01:38.858000Z",
  "file_hash": "299d6d480e99d0cd881c4487c72bf5df2519d20b16a801c40ad356ee0675384a",
  "private": false,
  "record": {
    "abstract": "We prove that any exact quantum algorithm searching an ordered list of N\nelements requires more than \\frac{1}{\\pi}(\\ln(N)-1) queries to the list. This\nimproves upon the previously best known lower bound of {1/12}\\log_2(N) - O(1).\n  Our proof is based on a weighted all-pairs inner product argument, and it\ngeneralizes to bounded-error quantum algorithms.\n  The currently best known upper bound for exact searching is roughly 0.526\n\\log_2(N).\n  We give an exact quantum algorithm that uses \\log_3(N) + O(1) queries, which\nis roughly 0.631 \\log_2(N). The main principles in our algorithm are an quantum\nparallel use of the classical binary search algorithm and a method that allows\nbasis states in superpositions to communicate.",
    "arxiv_id": "quant-ph/0009032",
    "authors": [
      "Peter Hoyer",
      "Jan Neerbek"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Bounds on quantum ordered searching",
    "url": "https://arxiv.org/abs/quant-ph/0009032"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "0d051440-ce06-472e-9916-4aceb8e261d2",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}