dorsal/arxiv
View SchemaRobust Quantum Algorithms with $\eps$-Biased Oracles
| Authors | Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi, Katsumasa Watanabe |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0605077 |
| URL | https://arxiv.org/abs/quant-ph/0605077 |
Abstract
This paper considers the quantum query complexity of {\it $\eps$-biased oracles} that return the correct value with probability only $1/2 + \eps$. In particular, we show a quantum algorithm to compute $N$-bit OR functions with $O(\sqrt{N}/{\eps})$ queries to $\eps$-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\eps}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper by Iwama et al. affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of $\eps$. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of $\eps$.
{
"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
}