Polynomial degree vs. quantum query complexity
Abstract
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.
23 pages, 1 figure, v4 "proof by old method" corrected, moderate changes to presentation elsewhere
23 pages, 1 figure, v4 "proof by old method" corrected, moderate changes to presentation elsewhere