Exponential Quantum Advantage in Testing Fourier Dimensionality

Kenny Chen

In the authors' words

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 $Θ (k)$ quantum property tester for this problem. With Gopalan \etal's classical lower bound of $Ω (2^{k /2})$ for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a $O ~ (2^{k /2} / ϵ)$ classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.

Main resultThe abstract does not state a limitation.

Exponential Quantum Advantage in Testing Fourier Dimensionality

In the authors' words

More on Quantum physics & computing that day

In-orbit operation of a programmable quantum photonic processor

Nonlocal advantage of quantum coherence in tau-lepton pairs from electron--positron collisions

Bridge of Ψ's: Quantum Circuit Optimization with Schr\"odinger Bridges

Quantum Advantage for Distributed Symmetry Breaking

Thermodynamic Proof of Quantumness without Structure

Bridge of $Ψ$ 's: Quantum Circuit Optimization with Schr\"odinger Bridges