k-Forrelation Optimally Separates Quantum and Classical Query Complexity

Aaronson and Ambainis (SICOMP `18) showed that any partial function on N bits that can be computed with an advantage δ over a random guess by making q quantum queries, can also be computed classically with an advantage δ/2 by a randomized decision tree making {O}<sub>q</sub>\(N^{1-frac{1}{2q}}δ<sup>-2</sup>\) queries. Moreover, they conjectured the k-Forrelation problem - a partial function that can be computed with q = lceil k/2 rceil quantum queries - to be a suitable candidate for exhibiting such an extremal separation. We prove their conjecture by showing a tight lower bound of widetildeΩ\(N<sup>1-1/k</sup>\) for the randomized query complexity of k-Forrelation, where the advantage δ= 2<sup>-O(k)</sup>. By standard amplification arguments, this gives an explicit partial function that exhibits an O_ε(1) vs Ω\(N<sup>1-ε</sup>\) separation between bounded-error quantum and randomized query complexities, where ε>0 can be made arbitrarily small. Our proof also gives the same bound for the closely related but non-explicit k-Rorrelation function introduced by Tal (FOCS `20). Our techniques rely on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, give a more general statement. We show that to prove lower bounds for k-Forrelation against a family of functions, it suffices to bound the ell₁-weight of the Fourier coefficients between levels k and (k-1)k. We also prove new interpolation and integration by parts identities that might be of independent interest in the context of rounding high-dimensional Gaussian vectors.