dorsal/arxiv
View SchemaQuantum Search on Bounded-Error Inputs
| Authors | Peter Hoyer, Michele Mosca, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0304052 |
| URL | https://arxiv.org/abs/quant-ph/0304052 |
| DOI | 10.1007/3-540-45061-0_25 |
| Journal | 30th Intl. Colloquium on Automata, Languages, and Programming (ICALP), LNCS 2719, pp. 291-299, 2003 |
Abstract
Suppose we have n algorithms, quantum or classical, each computing some bit-value with bounded error probability. We describe a quantum algorithm that uses O(sqrt{n}) repetitions of the base algorithms and with high probability finds the index of a 1-bit among these n bits (if there is such an index). This shows that it is not necessary to first significantly reduce the error probability in the base algorithms to O(1/poly(n)) (which would require O(sqrt{n}log n) repetitions in total). Our technique is a recursive interleaving of amplitude amplification and error-reduction, and may be of more general interest. Essentially, it shows that quantum amplitude amplification can be made to work also with a bounded-error verifier. As a corollary we obtain optimal quantum upper bounds of O(sqrt{N}) queries for all constant-depth AND-OR trees on N variables, improving upon earlier upper bounds of O(sqrt{N}polylog(N)).
{
"annotation_id": "fc9aee1b-260f-4b74-8ffd-9f0d7cb2acc9",
"date_created": "2026-03-02T18:02:00.217000Z",
"date_modified": "2026-03-02T18:02:00.217000Z",
"file_hash": "0d4d3c39658128bc0dd9db19dccc9748ff1f18bb3abc508fa35d7b503581f49c",
"private": false,
"record": {
"abstract": "Suppose we have n algorithms, quantum or classical, each computing some\nbit-value with bounded error probability. We describe a quantum algorithm that\nuses O(sqrt{n}) repetitions of the base algorithms and with high probability\nfinds the index of a 1-bit among these n bits (if there is such an index). This\nshows that it is not necessary to first significantly reduce the error\nprobability in the base algorithms to O(1/poly(n)) (which would require\nO(sqrt{n}log n) repetitions in total). Our technique is a recursive\ninterleaving of amplitude amplification and error-reduction, and may be of more\ngeneral interest. Essentially, it shows that quantum amplitude amplification\ncan be made to work also with a bounded-error verifier. As a corollary we\nobtain optimal quantum upper bounds of O(sqrt{N}) queries for all\nconstant-depth AND-OR trees on N variables, improving upon earlier upper bounds\nof O(sqrt{N}polylog(N)).",
"arxiv_id": "quant-ph/0304052",
"authors": [
"Peter Hoyer",
"Michele Mosca",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1007/3-540-45061-0_25",
"journal_ref": "30th Intl. Colloquium on Automata, Languages, and Programming\n (ICALP), LNCS 2719, pp. 291-299, 2003",
"title": "Quantum Search on Bounded-Error Inputs",
"url": "https://arxiv.org/abs/quant-ph/0304052"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "be014329-913e-4425-83d6-d02f2c2fa3ea",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}