Lower bounds for XOR of forrelations

The Forrelation problem, first introduced by Aaronson [1] and Aaronson and Ambainis [2], 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 [2]; the first separation between poly-logarithmic 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 [15]; and improved separations between quantum and classical communication complexity [12]. 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 (Equation presented). This is a strengthening of a result of [8], that gave a similar statement for k = 1, using the technique of [15]. 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 õ(N^1/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 [10, 12]. 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 constant-depth circuit has polynomially small advantage were known [15].