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

Abstract: 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 use approximate degree to prove optimal or nearly optimal lower bounds on the quantum query complexity of several problems, resolving open questions from prior work. The problems studied include k-distinctness, image size testing, k-junta testing, approximating statistical distance, approximating Shannon entropy, and surjectivity. This work was presented at QIP 2018 and STOC 2018, and is available at https://arxiv.org/abs/1710.09079. This is joint work with Mark Bun and Justin Thaler.