Quantum Algorithms for Learning and Testing Juntas

Alp Atici, Rocco A. Servedio

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…