Quantum algorithms for learning and testing juntas

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop efficient algorithms: (1) whose sample complexity has no dependence on n, the dimension of the domain the Boolean functions are defined over; (2) with no access to any classical or quantum membership (black-box) queries. Instead, our algorithms use only classical examples generated uniformly at random and fixed quantum superpositions of such classical examples; (3) which require only a few quantum examples but possibly many classical random examples (which are considered quite cheap relative to quantum examples). Our quantum algorithms are based on a subroutine FS which enables sampling according to the Fourier spectrum of f; the FS subroutine was used in earlier work of Bshouty and Jackson on quantum learning. Our results are as follows: (1) We give an algorithm for testing k-juntas to accuracy epsilon that uses O(k/is an element of) quantum examples. This improves on the number of examples used by the best known classical algorithm. ( 2) We establish the following lower bound: any FS-based k-junta testing algorithm requires Omega (root k) queries. (3) We give an algorithm for learning k-juntas to accuracy is an element of that uses O(is an element of(-1)k log k) quantum examples and O(2(k) log(1/is an element of)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound.