{
  "annotation_id": "508fb75a-f850-4bee-bdf9-0c12ea059de9",
  "date_created": "2026-03-02T18:02:36.802000Z",
  "date_modified": "2026-03-02T18:02:36.802000Z",
  "file_hash": "4aaefd25a61eda3aa6ba760b7798a954d04549c11f92b431d7402b1bef63ea77",
  "private": false,
  "record": {
    "abstract": "We use a Bayesian approach to optimally solve problems in noisy binary\nsearch. We deal with two variants:\n  1. Each comparison can be erroneous with some probability $1 - p$. 2. At each\nstage $k$ comparisons can be performed in parallel and a noisy answer is\nreturned\n  We present a (classic) algorithm which optimally solves both variants\ntogether, up to an additive term of O(\\log \\log(n)), and prove matching\ninformation theoretic lower bounds. We use the algorithm to improve the results\nof Farhi et al \\cite{FGGS99} presenting a quantum (error free) search algorithm\nin an ordered list of expected complexity less than (\\log_2n) / 3.",
    "arxiv_id": "quant-ph/0703231",
    "authors": [
      "M. Ben-Or",
      "Avinatan Hassidim"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Search in an Ordered List via Adaptive Learning",
    "url": "https://arxiv.org/abs/quant-ph/0703231"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "d275e4c5-d4ac-417c-a6c9-28e74c5dc28e",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}