An Optimal Separation of Randomized and Quantum Query Complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $\ell \ge 1$ sum to at most $c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}…