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 ε that uses O(k/ϵ) 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(\sqrt{k})\) queries. (3) We give an algorithm for learning k-juntas to accuracy ϵ that uses O(ϵ−1 k log k) quantum examples and O(2k log(1/ϵ)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ambainis A., Iwama K., Kawachi A., Masuda H., Putra R.H., and Yamashita S., in Proceedings of STACS 2004, pp. 93–104 (2003).
Atıcı A., Servedio R.A. (2005). Quantum Information Process. 4, 355–386
Bshouty N.H., Jackson J.C. (1999). SIAM J. Comp. 28, 1136–1153
J. Castro, in Proceedings of 17th ALT, pp. 78–92 (2006).
M. Hunziker, Meyer D.A., J. Park, J. Pommersheim, and M. Rothstein, The Geometry of Quantum Learning, arXiv:quant-ph/0309059; Quantum Information Processing (to appear).
K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita, Robust Quantum Algorithms for Oracle Identification, arXiv:quant-ph/0411204 (2005).
Servedio R.A., Gortler S.J. (2004). SIAM J. Comp. 33, 1067–1092
H. Buhrman, L. Fortnow, I. Newman, and H. Röhrig, in Proceedings of 14th SODA, pp. 480–488 (2003).
K. Friedl, F. Magniez, M. Santha, and P. Sen, in Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, pp. 419–428.
F. Magniez and A. Nayak, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pp. 1312–1324 (2005).
Jackson J.C. (1997). J. Comput. Syst. Sci. 55, 414–440
Valiant L.G. (1984). Commun. Assoc. Comp. Machinery 27, 1134–1142
J. Arpe and R. Reischuk, in Proceedings of the 14th International Conference on Algorithmic Learning Theory, pp. 99–113 (2003).
J. Arpe and R. Reischuk, in Proceedings of the 3rd International Conference on Theory and Applications of Models of Computation, pp. 387–398 (2006).
A. Blum, in Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop, pp. 731–733 (2003).
Chockler H., Gutfreund D. (2004). Information Process. Lett. 90, 301–305
E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 103–112 (2002).
R. Lipton, E. Markakis, A. Mehta, and N. Vishnoi, in Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 112–119 (2005).
Mossel E., O’Donnell R., Servedio R.A. (2004). J. Compu. Syst. Sci. 69, 421–434
J. Köbler and W. Lindner, Bull. EATCS 89 (2006).
Y. Mansour, Learning Boolean functions via the Fourier transform, in Theoretical Advances in Neural Computation and Learning (Kluwer Academic Publishers, 1994, pp. 391–424).
Kushilevitz E., Mansour Y. (1993). SIAM J. Comput. 22, 1331–1348
Goldreich O., Goldwasser S., Ron D. (1998). J. ACM 45, 653–750
Rubinfeld R., Sudan M. (1996). SIAM J. Comp. 25, 252–271
Kahn J., Kalai G., and Linial N., in Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp. 68–80 (1988).
Bernstein E., Vazirani U. (1997). SIAM J. Comp 26, 1411–1473
R. O’Donnell and R. A. Servedio, J. Comp System Sci, to appear. Available at http://www.cs.columbia.edu/∼rocco/papers/ccc03.htm.. Preliminary version appeared in Eighteenth Annual IEEE Conference on Computational Complexity, pp. 3–12 (2003).
Bshouty N., Cleve R., Gavaldà R., Kannan S., and Tamon C. (1996). J. Comp. Syst. Sci. 52, 421–433
Author information
Authors and Affiliations
Corresponding author
Additional information
Work done while at the Department of Mathematics, Columbia University, New York, NY 10027, USA.
Supported in part by NSF award CCF-0347282, by NSF award CCF-0523664, and by a Sloan Foundation Fellowship.
Rights and permissions
About this article
Cite this article
Atıcı, A., Servedio, R.A. Quantum Algorithms for Learning and Testing Juntas. Quantum Inf Process 6, 323–348 (2007). https://doi.org/10.1007/s11128-007-0061-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-007-0061-6
Keywords
- Juntas
- quantum query algorithms
- quantum property testing
- computational learning theory
- quantum computation
- lower bounds