论文标题
随机和量子查询复杂性的最佳分离
An Optimal Separation of Randomized and Quantum Query Complexity
论文作者
论文摘要
我们证明，对于每个决策树，给定订单$ \ ell \ geq1 $ sum的傅立叶系数的绝对值最多最多$ c^{\ ell} \ sqrt {\ binom {\ binom {d} {\ ell} {\ ell} {\ ell}（1+ \ log n） $ C> 0 $是绝对常数。该界限本质上是紧密的，并因TAL引起的猜想（Arxiv 2019; Focs 2020）。我们工作之前的界限迅速降级，$ \ ell，$已经在$ \ 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 $k$ and randomized query complexity $\tildeΩ(n^{1-\frac{1}{2k}}).$ This separation of bounded-error quantum versus randomized query complexity is best possible, by the Aaronson和Ambainis（Stoc 2015）和Bravyi，Gosset，Grier和Schaeffer的结果（2021）。在我们的工作之前，最著名的分离是多项式较弱的：$ o（1）$ vess $ω（n^{2/3-ε}）$对于任何$ε> 0 $（TAL，focs 2020）。 作为另一个应用程序，我们获得了$ o（\ log n）$的最佳分离，而$ω（n^{1-ε}）$用于有界误差量子与随机通信复杂性，对于任何$ε> 0，对于任何$ε> 0。
We prove that for every decision tree, the absolute values of the Fourier coefficients of a 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 $k$ and randomized query complexity $\tildeΩ(n^{1-\frac{1}{2k}}).$ This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi, Gosset, Grier, and Schaeffer (2021). 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).
