TY - GEN
T1 - k-forrelation optimally separates Quantum and classical query complexity
AU - Bansal, Nikhil
AU - Sinha, Makrand
N1 - Funding Information:
We thank Ronald de Wolf for discussions and for providing helpful feedback on the writing, Avishay Tal for useful comments and for encouraging us to extend our results to obtain the improved parameter δ = 2−O(k), and Arkadev Chattopadhyay and Suhail Sherif for pointing out the applications to communication complexity. This work was supported by the NWO VICI grant 639.023.812.
Publisher Copyright:
© 2021 Owner/Author.
PY - 2021/6/15
Y1 - 2021/6/15
N2 - 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 = 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 ?(N1-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 ?(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.
AB - 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 = 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 ?(N1-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 ?(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.
KW - Decision Trees
KW - Forrelation
KW - Gaussian Interpolation
KW - Quantum query complexity
KW - Stochastic Calculus
UR - http://www.scopus.com/inward/record.url?scp=85108155031&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108155031&partnerID=8YFLogxK
U2 - 10.1145/3406325.3451040
DO - 10.1145/3406325.3451040
M3 - Conference contribution
AN - SCOPUS:85108155031
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1303
EP - 1316
BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Khuller, Samir
A2 - Williams, Virginia Vassilevska
PB - Association for Computing Machinery
T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Y2 - 21 June 2021 through 25 June 2021
ER -