arXiv:2609.25816 · v4

Exponential Quantum Advantage in Testing Fourier Dimensionality

首次提交 2026-09-22 15:45

版本更新 2026-11-02 10:38

雷达观测 2026-11-04 23:42

摘要

A boolean function $f$ has Fourier dimension $k$ if its strings with nonzero Fourier coefficients span a subspace of dimension $k$. We first 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 an $O(k/\sqrtε)$-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of $Ω(2^{k/2})$, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity. We then introduce and study the tolerant version of this problem. That is, determining whether a function is $αε$-close to having Fourier dimension at most $k$, or is $ε$-far from being so. Perhaps surprisingly, we show that this tolerant version of the problem is essentially just as hard as the standard version of the problem. That is, we show this problem has a $\tilde{O}(k/ε)$ quantum tester, and a $\tilde{O}(2^{k/2}/ε)$ classical tester.

作者备注：38 pages; small fixes to existing sections, adding new sections on the tolerant version of the problem