{
  "annotation_id": "2750366d-f897-4028-be1f-5d2529854f2c",
  "date_created": "2026-03-02T18:02:26.588000Z",
  "date_modified": "2026-03-02T18:02:26.588000Z",
  "file_hash": "aba8535a995af5e2577a809ae01f238cb341b5d8419cc0cb33ea79ee164c8a7b",
  "private": false,
  "record": {
    "abstract": "This paper considers the quantum query complexity of {\\it $\\eps$-biased\noracles} that return the correct value with probability only $1/2 + \\eps$. In\nparticular, we show a quantum algorithm to compute $N$-bit OR functions with\n$O(\\sqrt{N}/{\\eps})$ queries to $\\eps$-biased oracles. This improves the known\nupper bound of $O(\\sqrt{N}/{\\eps}^2)$ and matches the known lower bound; we\nanswer the conjecture raised by the paper by Iwama et al. affirmatively. We\nalso show a quantum algorithm to cope with the situation in which we have no\nknowledge about the value of $\\eps$. This contrasts with the corresponding\nclassical situation, where it is almost hopeless to achieve more than a\nconstant success probability without knowing the value of $\\eps$.",
    "arxiv_id": "quant-ph/0605077",
    "authors": [
      "Tomoya Suzuki",
      "Shigeru Yamashita",
      "Masaki Nakanishi",
      "Katsumasa Watanabe"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Robust Quantum Algorithms with $\\eps$-Biased Oracles",
    "url": "https://arxiv.org/abs/quant-ph/0605077"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "9a4f557b-e690-4183-bc66-4a34631f276f",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}