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

Robin Kothari, Microsoft Research (PLEASE NOTE NEW DATE AND TIME)

We use the polynomial method 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.​ Paper available at https://arxiv.org/abs/1710.09079. This is joint work with Mark Bun and Justin Thaler.