A. Atici and R. Servedio.

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:

- whose sample complexity has no dependence on $n$, the dimension of the domain the Boolean functions are defined over;
- 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;
- which require only a few quantum examples but possibly many classical random examples (which are considered quite ``cheap'' relative to quantum examples).

- We give an algorithm for testing $k$-juntas to accuracy $\eps$ that uses $O(k/\epsilon)$ quantum examples. This improves on the number of examples used by the best known classical algorithm.
- We establish the following lower bound: any FS-based $k$-junta testing algorithm requires $\Omega(\sqrt{k})$ queries.
- We give an algorithm for learning $k$-juntas to accuracy $\eps$ that uses $O(\epsilon^{-1} k\log k)$ quantum examples and $O(2^k \log(1/\eps))$ random examples. We show that this learning algorithms is close to optimal by giving a related lower bound.

Click here to access the article