An Optimal Separation of Randomized and Quantum Query Complexity
An Optimal Separation of Randomized and Quantum Query Complexity
复制标题
随机和量子查询复杂性的最佳分离
DOI：
10.1145/3406325.3451019
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wu, Pei
中科院分区：
文献类型：
--
作者：
Sherstov, Alexander A.;Storozhenko, Andrey A.;Wu, Pei
本文证明了对于每一棵决策树，给定阶数t ≥1的Fourier系数的绝对值之和至多为（cd/t）t/2（1+logn）（t−1）/2，其中r是变量个数，di是树的深度，c>0是一个绝对常数.这个界限本质上是紧的，并且解决了Tal的猜想（arxiv 2019; FOCS 2020）。作为应用，我们得到了对任意整数k ≥1，一个关于nbits的部分布尔函数，它的有界错误量子查询复杂度最多为nk/2 <$k，随机查询复杂度为Ω（n1−1/k）。根据Aaronson和Ambainis（STOC 2015）的结果，这种有界错误量子与随机查询复杂性的分离是最好的。在我们的工作之前，最著名的分离是多项式较弱的：O（1）与Ω（n2/3− n）对于任何n>0（Tal，FOCS 2020）.作为另一个应用，我们获得了O（logn）与Ω（n1− n）对于有界错误量子与随机通信复杂度的基本最优分离，对于任何n>0。之前最好的分离是多项式弱的：O（logn）vs Ω（n2/3− Ω）（隐含在Tal，FOCS 2020中）。
We prove that for every decision tree, the absolute values of the Fourier coefficients of given ordert≥1 sum to at most (cd/t)t/2(1+logn)(t−1)/2, wherenis the number of variables,dis the tree depth, andc>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 witht, becoming trivial already att=√d.As an application, we obtain, for every integerk≥1, a partial Boolean function onnbits that has bounded-error quantum query complexity at most ⌈k/2⌉ and randomized query complexity Ω(n1−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 Ω(n2/3−є) for any є>0 (Tal, FOCS 2020).As another application, we obtain an essentially optimal separation ofO(logn) versus Ω(n1−є) for bounded-error quantum versus randomized communication complexity, for any є>0. The best previous separation was polynomially weaker:O(logn) versus Ω(n2/3−є) (implicit in Tal, FOCS 2020).