Lower bounds for XOR of forrelations

Uma Girish, Ran Raz, Wei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 õ(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 [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 languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
EditorsMary Wootters, Laura Sanita
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772075
DOIs
StatePublished - Sep 1 2021
Event24th 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 2021Aug 18 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume207
ISSN (Print)1868-8969

Conference

Conference24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021
Country/TerritoryUnited States
CityVirtual, Seattle
Period8/16/218/18/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Forrelation
  • Quantum versus classical
  • Quasipolynomial
  • Separation
  • XOR

Fingerprint

Dive into the research topics of 'Lower bounds for XOR of forrelations'. Together they form a unique fingerprint.

Cite this