Clément Canonne @ccanonne.github.io · Apr 17 The polynomial method (to prove quantum query lower bounds) is so elegant. 1. Any q-query quantum algo maps to a deg-(2q) polynomial p. 2. p must take high values on "yes" inputs and low values on "no" inputs. 3. Forget quantum: prove no low-degree polynomial can do that. (Say "Chebyshev" 3 times.)
21 likes 2 replies
?
Replies
Furthermore this polynomial must take values between 0 and 1 on all possible inputs.
(This was prompted by us* reviewing the polynomial method in a reading group yesterday) More on this: see, e.g., Lectures 11 and 12 here: www.cs.cmu.edu/~odonnell/qu... (lecture notes by @booleananalysis.bsky.social and John Wright) *led by Kenny Chen, PhD student in our group