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 \cite{DBLP:journals/siamcomp/GopalanOSSW11}. We complement this result with a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.25816
curl -X POST /api/v1/records/arxiv/2609.25816/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.25816/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'