Quantum testing beats classical methods exponentially for Fourier analysis
Exponential Quantum Advantage in Testing Fourier Dimensionality
Computational ComplexityData Structures and Algorithms
Summary
This paper studies how quickly one can check if a function's main features fit into a small-dimensional space using Fourier analysis. The authors show that quantum computing can do this much faster—exponentially faster—than classical methods for a certain technical measure called Fourier dimension. They also improve classical algorithms to nearly match the lower bounds, confirming the quantum advantage is real and significant. This finding highlights a concrete task where quantum computers outperform traditional ones.
What this means in practice
- •For quantum algorithm developers: Design more efficient quantum tests for functions' structural properties in data analysis.
- •For complexity theorists: Refine the understanding of quantum versus classical testers' efficiency for function property problems.
A theory result. No direct application yet.
Authors
Kenny Chen
Abstract
A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is a $Θ(k)$ quantum property tester for this problem. With Gopalan \etal's classical lower bound of $Ω(2^{k/2})$ for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.