论文标题
XOR的下限
Lower Bounds for XOR of Forrelations
论文作者
论文摘要
在分离量子和经典模型的背景下，Aaronson [A10]和Aaronson和Ambainis [AA15]引入的FORRASATION问题是一个精心研究的问题。该问题的变体用于给出量子和经典查询复杂性之间的指数分离[A10，AA15]；量子查询复杂性和有界深度电路[RT19]；以及量子和古典交流复杂性[GRT19]。在所有这些分离中，经典模型的下限仅在协议的优势（在随机猜测的情况下）超过$ \ 1/\ sqrt {n} $，即，成功概率大于$ \ \ \ \ 1/2 + 1/\ sqrt {n} $。为了在经典协议具有较小的优势时实现分离，我们在这项工作中研究了$ k $独立副本（其中$ k \ ll n $）的XOR。我们证明了一个非常普遍的结果，该结果表明，任何在限制下关闭的布尔式函数家族，其傅立叶质量为$ 2K $的傅立叶质量由$α^k $限制，无法计算出$ k $的XOR XOR XOR的XOR XOR，具有优势的$ K $独立副本，其优势比$ O \ weft（\ frac {\ frac {α^k} n^n^n^n^n^k/2}}}}这是[CHLT19]的结果的加强，它使用[RT19]的技术给出了$ k = 1 $的类似结果。作为结果的应用，我们给出了一个部分布尔函数的第一个示例，可以通过同时发音的量子协议来计算，成本的$ \ mbox {polylog}（n）$（当玩家共享$ \ mbox {polylog}（polylog}（polylog}（n）$ epr Pairs） $ \ tilde {o}（n^{1/4}）$，在随机猜测中具有quasipolynomomenty上很小的优势。我们还给出了部分布尔函数的第一个示例，该函数具有成本$ \ mbox {polylog}（n）$的量子查询算法，因此，在随机猜测的情况下，任何固定型大小的恒定恒定电路都具有quasipolynomem上的小优势。
The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variants of this problem were used to give exponential separations between quantum and classical query complexity [A10, AA15]; quantum query complexity and bounded-depth circuits [RT19]; and quantum and classical communication complexity [GRT19]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than $\approx 1/\sqrt{N}$, that is, the success probability is larger than $\approx 1/2 + 1/\sqrt{N}$. To achieve separations when the classical protocol has smaller advantage, we study in this work the XOR of $k$ independent copies of the Forrelation function (where $k\ll N$). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level $2k$ is bounded by $α^k$, cannot compute the XOR of $k$ independent copies of the Forrelation function with advantage better than $O\left(\frac{α^k}{N^{k/2}}\right)$. This is a strengthening of a result of [CHLT19], that gave a similar result for $k=1$, using the technique of [RT19]. As an application of our result, we give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol of cost $\mbox{polylog}(N)$ (when players share $\mbox{polylog}(N)$ EPR pairs), however, any classical interactive randomized protocol of cost at most $\tilde{o}(N^{1/4})$, has quasipolynomially small advantage over a random guess. We also give the first example of a partial Boolean function that has a quantum query algorithm of cost $\mbox{polylog}(N)$, and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.
