dorsal/arxiv
View SchemaPolynomial degree vs. quantum query complexity
| Authors | Andris Ambainis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0305028 |
| URL | https://arxiv.org/abs/quant-ph/0305028 |
| Journal | Journal of Computer and System Sciences, 72(2): 220-238, 2006 |
Abstract
The degree of a polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity \Omega(M^{1.321...}). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.
{
"annotation_id": "84fba82c-b699-4452-999f-4134d20532f1",
"date_created": "2026-03-02T18:02:00.293000Z",
"date_modified": "2026-03-02T18:02:00.293000Z",
"file_hash": "40912ac783328e1be292e487ce16bbd14ae4ce4c79b6f3b1d6ed6d541f8c042d",
"private": false,
"record": {
"abstract": "The degree of a polynomial representing (or approximating) a function f is a\nlower bound for the number of quantum queries needed to compute f. This\nobservation has been a source of many lower bounds on quantum algorithms. It\nhas been an open problem whether this lower bound is tight.\n We exhibit a function with polynomial degree M and quantum query complexity\n\\Omega(M^{1.321...}). This is the first superlinear separation between\npolynomial degree and quantum query complexity. The lower bound is shown by a\nnew, more general version of quantum adversary method.",
"arxiv_id": "quant-ph/0305028",
"authors": [
"Andris Ambainis"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Journal of Computer and System Sciences, 72(2): 220-238, 2006",
"title": "Polynomial degree vs. quantum query complexity",
"url": "https://arxiv.org/abs/quant-ph/0305028"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4e716b88-0a0c-4a4c-9375-6d5c52fca1ab",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}