Abstract
Many properties of Boolean functions can be tested far more efficiently thanthe function can be learned. However, this advantage often disappears whentesters are limited to random samples--a natural setting for datascience--rather than queries. In this work we investigate the quantum versionof this scenario: quantum algorithms that test properties of a function $f$solely from quantum data in the form of copies of the function state for $f$. For three well-established properties, we show that the speedup lost whenrestricting classical testers to samples can be recovered by testers that usequantum data. For monotonicity testing, we give a quantum algorithm that uses$\tilde{\mathcal{O}}(n^2)$ function state copies as compared to the$2^{\Omega(\sqrt{n})}$ samples required classically. We also present$\mathcal{O}(1)$-copy testers for symmetry and triangle-freeness, comparingfavorably to classical lower bounds of $\Omega(n^{1/4})$ and $\Omega(n)$samples respectively. These algorithms are time-efficient and necessarilyinclude techniques beyond the Fourier sampling approaches applied to earliertesting problems. These results make the case for a general study of the advantages afforded byquantum data for testing. We contribute to this project by complementing ourupper bounds with a lower bound of $\Omega(1/\varepsilon)$ for monotonicitytesting from quantum data in the proximity regime$\varepsilon\leq\mathcal{O}(n^{-3/2})$. This implies a strict separationbetween testing monotonicity from quantum data and from quantum queries--where$\tilde{\mathcal{O}}(n)$ queries suffice when $\varepsilon=\Theta(n^{-3/2})$.We also exhibit a testing problem that can be solved from $\mathcal{O}(1)$classical queries but requires $\Omega(2^{n/2})$ function state copies,complementing a separation of the same magnitude in the opposite directionderived from the Forrelation problem.