{"id":"arxiv/2609.25816","url":"https://arxiv.org/abs/2609.25816","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Exponential Quantum Advantage in Testing Fourier Dimensionality","domain":"quant-ph","source":"arxiv","authors":["Kenny Chen"],"reviews":0,"subject":"quant-ph","summary":"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 \\cite{DBLP:journals/siamcomp/GopalanOSSW11}. We complement this result with a…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}