Quantum Algorithms for Learning and Testing Juntas
| dc.creator | Atici, Alp | |
| dc.creator | Servedio, Rocco A. | |
| dc.date | 2007-07-24 | |
| dc.date.accessioned | 2026-07-07T08:36:09Z | |
| dc.date.available | 2026-07-07T08:36:09Z | |
| dc.description | 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: - 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 $ε$ that uses $O(k/ε)$ 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 $Ω(\sqrt{k})$ queries. - We give an algorithm for learning $k$-juntas to accuracy $ε$ that uses $O(ε^{-1} k\log k)$ quantum examples and $O(2^k \log(1/ε))$ random examples. We show that this learning algorithms is close to optimal by giving a related lower bound. | |
| dc.description | 15 pages, 1 figure. Uses synttree package. To appear in Quantum Information Processing | |
| dc.identifier | https://arxiv.org/abs/0707.3479 | |
| dc.identifier | http://arxiv.org/abs/0707.3479 | |
| dc.identifier | Quantum Information Processing, Vol. 6, No. 5, 323 - 348 (2007) | |
| dc.identifier | doi:10.1007/s11128-007-0061-6 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/139968 | |
| dc.subject | Quantum Physics | |
| dc.subject | Machine Learning | |
| dc.title | Quantum Algorithms for Learning and Testing Juntas | |
| dc.type | text |