Exponential Quantum Advantage in Testing Fourier Dimensionality
This work considers the property testing task of determining whether a function has Fourier dimension at most $k, or is $\epsilon$-far from being so, and shows that there is an $O(k/\sqrt{\epsilon})$-query quantum property tester for this problem, which is shown to be almost optimal.