## Abstract

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].

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021 |

Editors | Mary Wootters, Laura Sanita |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772075 |

DOIs | |

State | Published - Sep 1 2021 |

Event | 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 - Virtual, Seattle, United States Duration: Aug 16 2021 → Aug 18 2021 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 207 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 |
---|---|

Country/Territory | United States |

City | Virtual, Seattle |

Period | 8/16/21 → 8/18/21 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Forrelation
- Quantum versus classical
- Quasipolynomial
- Separation
- XOR