ECCC-Report TR20-128https://eccc.weizmann.ac.il/report/2020/128Comments and Revisions published for TR20-128en-usThu, 03 Sep 2020 16:24:26 +0300
Paper TR20-128
| An Optimal Separation of Randomized and Quantum Query Complexity |
Alexander A. Sherstov,
Andrey Storozhenko,
Pei Wu
https://eccc.weizmann.ac.il/report/2020/128We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\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 any positive integer $k,$ a partial Boolean function on $n$ bits that has bounded-error quantum query complexity at most $\lceil k/2\rceil$ and randomized query complexity $\tilde{\Omega}(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-\epsilon}$ for any $\epsilon>0$ (Tal, FOCS 2020).Thu, 03 Sep 2020 16:24:26 +0300https://eccc.weizmann.ac.il/report/2020/128