Quantum Algorithms for Learning and Testing Juntas.
A. Atici and R. Servedio.
Quantum Information Processing, 6(5): 323--348, 2007.


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:

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:

Click here to access the article

Back to main papers page