2020/08/16 by Nikhil Bansal, Bansal, Nikhil, Makrand Sinha +1 · 6 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.2008.07003
40 pages, 2 figures. Change from v1 to v2: Updated figures to fix an Adobe Acrobat specific issue. Change from v0 to v1: Improved the advantage $δ$ to $2^{-O(k)}$ strengthening the main conclusions. Added a reference to the independent work of Sherstov, Storozhenko and Wu (arxiv:2008.10223) who obtained a similar lower bound for the randomized query complexity of $k$-Rorrelation
arxiv created 2020/11/17 · arxiv updated 2020/11/18
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 Oq(N1-(1)/(2q)δ-2) 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Ω(N1-1/k) for the randomized query complexity of k-Forrelation, where the advantage δ= 2-O(k). By standard amplification arguments, this gives an explicit partial function that exhibits an Oε(1) vs Ω(N1-ε) 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.