期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-30
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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(N 1− 1 2q δ −2 ) queries. Moreover, they conjectured the k-Forrelation problem — a partial function that can be computed with q = dk/2e quantum queries — to be a suitable candidate for exhibiting such an extremal separation. We prove their conjecture by showing a tight lower bound of Ωek(N 1−1/k) for the randomized query complexity of k-Forrelation, where the advantage δ = 1/polylogk (N) and Ωek hides polylogk (N) factors. Our proof relies on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, shows a more general statement, that to prove lower bounds for k-Forrelation against a family of functions, it suffices to bound the `1-weight of the Fourier coefficients at levels k, 2k, 3k, . . . ,(k − 1)k for functions in the family.
