dorsal/arxiv
View SchemaQuantum Lower Bounds by Polynomials
| Authors | Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9802049 |
| URL | https://arxiv.org/abs/quant-ph/9802049 |
Abstract
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
{
"annotation_id": "1d5f020d-3981-4c37-97c3-845f80b9ec50",
"date_created": "2026-03-02T18:02:41.302000Z",
"date_modified": "2026-03-02T18:02:41.302000Z",
"file_hash": "6191277657bb927a272a1aead8cab142a7390e58f25c6db641d5152138e7749d",
"private": false,
"record": {
"abstract": "We examine the number T of queries that a quantum network requires to compute\nseveral Boolean functions on {0,1}^N in the black-box model. We show that, in\nthe black-box model, the exponential quantum speed-up obtained for partial\nfunctions (i.e. problems involving a promise on the input) by Deutsch and Jozsa\nand by Simon cannot be obtained for any total function: if a quantum algorithm\ncomputes some total Boolean function f with bounded-error using T black-box\nqueries then there is a classical deterministic algorithm that computes f\nexactly with O(T^6) queries.\n We also give asymptotically tight characterizations of T for all symmetric f\nin the exact, zero-error, and bounded-error settings. Finally, we give new\nprecise bounds for AND, OR, and PARITY. Our results are a quantum extension of\nthe so-called polynomial method, which has been successfully applied in\nclassical complexity theory, and also a quantum extension of results by Nisan\nabout a polynomial relationship between randomized and deterministic decision\ntree complexity.",
"arxiv_id": "quant-ph/9802049",
"authors": [
"Robert Beals",
"Harry Buhrman",
"Richard Cleve",
"Michele Mosca",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Quantum Lower Bounds by Polynomials",
"url": "https://arxiv.org/abs/quant-ph/9802049"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6fb49a5b-838c-4324-89f4-3ec998299157",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}