An Optimal Separation of Randomized and Quantum Query Complexity

Understanding the relative power of quantum and classical computing is of basic importance in theoretical computer science. In this talk, I will discuss an optimal separation of quantum and randomized complexities in the query model. First, we show the upper bound on the sum of the absolute values of the Fourier coefficients of given order $\ell$ for an arbitrary decision tree. The bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). This result is of interest in its own right, independent of its use to obtain optimal quantum-classical separations. As an application, we obtain, for any positive integer $k$, a partial Boolean function on $n$ bits that has bounded-error quantum query complexity at most $k/2$ and randomized query complexity $\Omega(n^{1-1/k})$ (up to polylogarithmic factors). 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-\epsilon}$ for any $\epsilon>0$ (Tal, FOCS 2020).