The polynomial method strikes back: tight quantum query bounds via dual polynomials
Mark Bun, Robin Kothari, Justin Thaler · 2018
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. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001).