Exponential Quantum Advantage in Testing Fourier Dimensionality

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 O(k/sqrtε) -query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan et al.'s classical lower bound of Ω(2 k/2), this demonstrates an exponential quantum advantage for this task. We complement this result with a (2 k/2/ε) classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity.