dorsal/arxiv
View SchemaAverage-Case Quantum Query Complexity
| Authors | Andris Ambainis, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9904079 |
| URL | https://arxiv.org/abs/quant-ph/9904079 |
Abstract
We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.
{
"annotation_id": "86cbc864-f3e5-41a1-ac98-76cd6db58004",
"date_created": "2026-03-02T18:02:45.127000Z",
"date_modified": "2026-03-02T18:02:45.127000Z",
"file_hash": "f8dfd4624c990e36993916a563c456ec4167e24c01a0fa444b84ed65d4a5f0d0",
"private": false,
"record": {
"abstract": "We compare classical and quantum query complexities of total Boolean\nfunctions. It is known that for worst-case complexity, the gap between quantum\nand classical can be at most polynomial. We show that for average-case\ncomplexity under the uniform distribution, quantum algorithms can be\nexponentially faster than classical algorithms. Under non-uniform distributions\nthe gap can even be super-exponential. We also prove some general bounds for\naverage-case complexity and show that the average-case quantum complexity of\nMAJORITY under the uniform distribution is nearly quadratically better than the\nclassical complexity.",
"arxiv_id": "quant-ph/9904079",
"authors": [
"Andris Ambainis",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Average-Case Quantum Query Complexity",
"url": "https://arxiv.org/abs/quant-ph/9904079"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4500c8b2-d71a-4b33-9237-d0c04bed40b1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}