k-forrelation optimally separates Quantum and classical query complexity

Nikhil Bansal, Makrand Sinha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Pages1303-1316
Number of pages14
ISBN (Electronic)9781450380539
DOIs
StatePublished - Jun 15 2021
Externally publishedYes
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/TerritoryItaly
CityVirtual, Online
Period6/21/216/25/21

Keywords

  • Decision Trees
  • Forrelation
  • Gaussian Interpolation
  • Quantum query complexity
  • Stochastic Calculus

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'k-forrelation optimally separates Quantum and classical query complexity'. Together they form a unique fingerprint.

Cite this