Quantum Algorithms for Learning and Testing Juntas.
A. Atici and
R. Servedio.
Quantum Information Processing, 6(5): 323--348, 2007.
Abstract:
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).
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:
-
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
Back to
main papers page