The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

Understand

The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3.

• Approximate degree is known to be a lower bound on quantum query complexity.
• We resolve or nearly resolve the approximate degree and quantum query complexities of the following basic functions: $\bullet$ $k$-distinctness: For any constant $k$, the approximate degree and quantum query complexity of $k$-distinctness is $\Omega(n^{3/4-1/(2k)})$.
• This is nearly tight for large $k$ (Belovs, FOCS 2012).