Quantum algorithms for learning and testing juntas (Q2462663)

This article considers quantum algorithms for testing and learning juntas, i.e.\ Boolean functions depending only on unknown sets of \(k\) out of \(n\) input variables. It introduces, and proves nearly optimal, a junta-learning algorithm with sample complexity independent of \(n\) requiring neither classical nor quantum membership (``black-box'') queries. Instead, to achieve a fixed accuracy, the algorithm requires only \(O(2^k)\) uniformly random classical examples together with \(O(k\log k)\) ``Fourier samples.'' (A Fourier sample produces a subset of \(\{1, \ldots, n\}\) drawn according to the unknown function's Fourier spectrum; it can be implemented on a quantum computer but is weaker than a quantum membership query.) Also introduced is a junta-testing algorithm with Fourier sample complexity linear in \(k\) for fixed accuracy; this improves on the best known classical membership query complexity.