An Optimal Separation of Randomized and Quantum Query Complexity

We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order ellgeq1 sum to at most c^ellsqrt{binom{d}{ell}\(1+log n\)^ell-1}, where n is the number of variables, d is the tree depth, and c>0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with ell, becoming trivial already at ell=sqrt{d}. As an application, we obtain, for every integer kgeq1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k and randomized query complexity Ω\(n^{1-frac{1}{2k}}\). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi, Gosset, Grier, and Schaeffer (2021). Prior to our work, the best known separation was polynomially weaker: O(1) versus Ω\(n^2/3-ε\) for any ε>0 (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of O\(log n\) versus Ω\(n^1-ε\) for bounded-error quantum versus randomized communication complexity, for any ε>0. The best previous separation was polynomially weaker: O\(log n\) versus Ω\(n^2/3-ε\) (implicit in Tal, FOCS 2020).