k-forrelation optimally separates Quantum and classical query complexity

DOI10.1145/3406325.3451040arXiv2008.07003WikidataQ130912987 ScholiaQ130912987MaRDI QIDQ6065254FDOQ6065254

Authors: N. Bansal, Makrand Sinha 

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Aaronson and Ambainis (SICOMP `18) showed that any partial function on $N$ bits that can be computed with an advantage $delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $delta/2$ by a randomized decision tree making $O_q(N^{1-frac12q}delt{a}^{-2})$ queries. Moreover, they conjectured the $k$-Forrelation problem -- a partial function that can be computed with $q=lceilk/2ceil$ quantum queries -- to be a suitable candidate for exhibiting such an extremal separation. We prove their conjecture by showing a tight lower bound of $widetildeOmega(N^{1-1/k})$ for the randomized query complexity of $k$-Forrelation, where the advantage $delta=2^{-O(k)}$. By standard amplification arguments, this gives an explicit partial function that exhibits an $O_{e}psilon(1)$ vs $Omega(N^{1-epsilon})$ separation between bounded-error quantum and randomized query complexities, where $epsilon>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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/2008.07003

zbMATH Keywords

decision treesquantum query complexityGaussian interpolationstochastic calculusforrelation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (6)

• Beyond quadratic speedups in quantum attacks on symmetric schemes
• Following forrelation -- quantum algorithms in exploring Boolean functions' spectra
• Sharp quantum versus classical query complexity separations
• Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms
• Quantum cryptography in Algorithmica
• Cnot-based design and query management in quantum relational databases

This page was built for publication: k-forrelation optimally separates Quantum and classical query complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065254)