Exponential Quantum Advantage in Testing Fourier Dimensionality
En palabras de los autores
A boolean function has Fourier dimension if its nonzero Fourier coefficients span a subspace of dimension . We consider the property testing task of determining whether a function has Fourier dimension at most , or is -far from being so. We show that there is a quantum property tester for this problem. With Gopalan \etal's classical lower bound of for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.
Resultado principalEl resumen no menciona limitaciones.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 20 pages