期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-36
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The Forrelation problem, first introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between polylogarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH [RT19]; and improved separations between 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 ≈ 1/ √ N, that is, the success probability is larger than ≈ 1/2 1/ √ N. This is unavoidable as ≈ 1/ √ N is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage ≈ 1/ √ N, in all these models. To achieve separations when the classical protocol has smaller advantage, we study in this work the xor of k independent copies of (a variant of) the Forrelation function (where k 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 (that is, the sum of the absolute values of all Fourier coefficients at level 2k is bounded by α k ), cannot compute the xor of k independent copies of the Forrelation function with advantage better than O α k Nk/2 . This is a strengthening of a result of [CHLT19], that gave a similar statement for k = 1, using the technique of [RT19]. We give several applications of our result. In particular, we obtain the following separations: Quantum versus Classical Communication Complexity: We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where Alice and Bob also share polylog(N) EPR pairs), and such that, any classical randomized protocol of communication complexity at most ˜o(N1/4 ), with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [G16, GRT19]. Quantum Query Complexity versus Bounded Depth Circuits: We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity polylog(N), and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constantdepth circuit has polynomially small advantage were known [RT19].
