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_q(N^{1−1/2q}δ^{−2}) queries. Moreover, they conjectured the k-Forrelation problem --- a partial function that can be computed with q=⌈k/2⌉ quantum queries --- to be a suitable candidate for exhibiting such an extremal separation. We prove their conjecture by showing a tight lower bound of \tilde{Ω}(N^{1−1/k}) for the randomized query complexity of k-Forrelation, where δ=2^{−O(k)}. By standard amplification arguments, this gives an explicit partial function that exhibits an O_ϵ(1) vs Ω(N^{1−ϵ}) 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 ℓ_1-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.

, , , ,
53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Bansal, N., & Sinha, M. (2021). k-Forrelation optimally separates quantum and classical query complexity. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (pp. 1303–1316). doi:10.1145/3406325.3451040