REVIEW
Polynomial degree vs. quantum query complexity
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Discussion (0). Sign in to comment.