An Optimal Separation of Randomized and Quantum Query Complexity
share
We prove that for every decision tree, the absolute values of the Fourier coefficients of given order ℓ≥1 sum to at most c^ℓ√(dℓ(1+log n)^ℓ-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 ℓ, becoming trivial already at ℓ=√(d). As an application, we obtain, for every integer k≥1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most ⌈ k/2⌉ and randomized query complexity Ω̃(n^1-1/k). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). 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).
READ FULL TEXT