ECCC-Report TR20-128https://eccc.weizmann.ac.il/report/2020/128Comments and Revisions published for TR20-128en-usFri, 20 Nov 2020 08:53:12 +0200
Revision 1
| An Optimal Separation of Randomized and Quantum Query Complexity |
Alexander A. Sherstov,
Andrey Storozhenko,
Pei Wu
https://eccc.weizmann.ac.il/report/2020/128#revision1We 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{\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 $k\geq1,$ 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 $\Omega(n^{2/3-\epsilon})$ for any $\epsilon>0$ (Tal, FOCS 2020).
As another application, we obtain an essentially optimal separation of $O(\log n)$ versus $\Omega(n^{1-\epsilon})$ for bounded-error quantum versus randomized communication complexity, for any $\epsilon>0.$ The best previous separation was polynomially weaker: $O(\log n)$ versus $\Omega(n^{2/3-\epsilon})$ (implicit in Tal, FOCS 2020).Fri, 20 Nov 2020 08:53:12 +0200https://eccc.weizmann.ac.il/report/2020/128#revision1
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