k-forrelation optimally separates Quantum and classical query complexity

DOI10.1145/3406325.3451040MaRDI QIDQ6065254zbMATH OpenWikidataFDO

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)

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)

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.

Cited in

(6)

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

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)