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 ℓ ≥slant 1 sum to at most (Equation presented), 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 [Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. The bounds prior to our work degraded rapidly with ℓ, becoming trivial already at ℓ = √d. As an application, we obtain, for every integer k ≥slant 1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k and randomized query complexity Ω(n^1- 2¹k). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [SIAM J. Comput., 47 (2018), pp. 982-1038] and Bravyi et al. [Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: O(1) versus Ω(n^2/3-∊) for any ∊ > 0 [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. 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-∊) (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]).