Polynomial degree vs. quantum query complexity
| dc.creator | Ambainis, Andris | |
| dc.date | 2003-05-06 | |
| dc.date | 2004-11-23 | |
| dc.date.accessioned | 2026-07-07T09:38:05Z | |
| dc.date.available | 2026-07-07T09:38:05Z | |
| dc.description | 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 Ω(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. | |
| dc.description | 23 pages, 1 figure, v4 "proof by old method" corrected, moderate changes to presentation elsewhere | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0305028 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0305028 | |
| dc.identifier | Journal of Computer and System Sciences, 72(2): 220-238, 2006 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160684 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Polynomial degree vs. quantum query complexity | |
| dc.type | text |