dorsal/arxiv
View SchemaQuantum Oracle Interrogation: Getting all information for almost half the price
| Authors | Wim van Dam |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9805006 |
| URL | https://arxiv.org/abs/quant-ph/9805006 |
| DOI | 10.1109/SFCS.1998.743486 |
| Journal | Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 362-367 (1998) |
Abstract
Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+sqrt(N) queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(sqrt(N)) oracle queries. In the second part of the article `approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.
{
"annotation_id": "03ee2bb6-a926-47d9-af45-e0f7760fdd21",
"date_created": "2026-03-02T18:02:41.489000Z",
"date_modified": "2026-03-02T18:02:41.489000Z",
"file_hash": "df3d31997dc513baa1d78a31ffc059f46f1ca8979957eafce03b89e8ce7a9b93",
"private": false,
"record": {
"abstract": "Consider a quantum computer in combination with a binary oracle of domain\nsize N. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess\nthe whole content of the oracle (being an N bit string) with probability\ngreater than 95%. This contrasts the power of classical computers which would\nrequire N calls to achieve the same task. From this result it follows that any\nfunction with the N bits of the oracle as input can be calculated using\nN/2+sqrt(N) queries if we allow a small probability of error. It is also shown\nthat this error probability can be made arbitrary small by using N/2+O(sqrt(N))\noracle queries.\n In the second part of the article `approximate interrogation\u0027 is considered.\nThis is when only a certain fraction of the N oracle bits are requested. Also\nfor this scenario does the quantum algorithm outperform the classical\nprotocols. An example is given where a quantum procedure with N/10 queries\nreturns a string of which 80% of the bits are correct. Any classical protocol\nwould need 6N/10 queries to establish such a correctness ratio.",
"arxiv_id": "quant-ph/9805006",
"authors": [
"Wim van Dam"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1109/SFCS.1998.743486",
"journal_ref": "Proceedings of the 39th Annual IEEE Symposium on Foundations of\n Computer Science (FOCS), pages 362-367 (1998)",
"title": "Quantum Oracle Interrogation: Getting all information for almost half the price",
"url": "https://arxiv.org/abs/quant-ph/9805006"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "802e2b7d-f59e-4074-a276-86b1b097465a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}