Quantum algorithms for learning and testing juntas

DOI10.1007/S11128-007-0061-6MaRDI QIDQ2462663zbMATH OpenOpenAlexFDO

Authors Alp Atıcı, Rocco A. Servedio

Publication date 3 December 2007

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.3479

zbMATH Keywords

computational learning theoryFourier samplejuntaquantum algorithmquantum property testing

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Quantum computation (81P68)

Abstract: 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 $epsilon$ 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(sqrtk)$ queries. - We give an algorithm for learning $k$-juntas to accuracy $epsilon$ that uses $O(epsilo{n}^{-1}klogk)$ quantum examples and $O(2^{k}log(1/epsilon))$ random examples. We show that this learning algorithms is close to optimal by giving a related lower bound.

Review text

This article considers quantum algorithms for testing and learning juntas, i.e.\ Boolean functions depending only on unknown sets of \(k\) out of \(n\) input variables. It introduces, and proves nearly optimal, a junta-learning algorithm with sample complexity independent of \(n\) requiring neither classical nor quantum membership (``black-box) queries. Instead, to achieve a fixed accuracy, the algorithm requires only \(O(2^k)\) uniformly random classical examples together with \(O(k\log k)\) ``Fourier samples. (A Fourier sample produces a subset of \(\{1, \ldots, n\}\) drawn according to the unknown function's Fourier spectrum; it can be implemented on a quantum computer but is weaker than a quantum membership query.) Also introduced is a junta-testing algorithm with Fourier sample complexity linear in \(k\) for fixed accuracy; this improves on the best known classical membership query complexity.

Recommendations

• Quantum algorithms for learning symmetric juntas via the adversary bound
• Quantum algorithm for distribution-free junta testing
• An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
• An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product
• An exact quantum algorithm for the 2-junta problem

Cites work

• A lower bound for testing juntas
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Automata, Languages and Programming
• Equivalences and Separations Between Quantum and Classical Learnability
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• Improved Algorithms for Quantum Identification of Boolean Oracles
• Improved bounds on quantum learning algorithms
• Learning Decision Trees Using the Fourier Spectrum
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Learning functions of \(k\) relevant variables
• Oracles and queries that are sufficient for exact learning
• Property testing and its connection to learning and approximation
• Quantum Complexity Theory
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust inference of relevant attributes
• Theory and Applications of Models of Computation

Cited in

(35)

• Quantum cryptographic property testing of multi-output Boolean functions
• Quantum learning of concentrated Boolean functions
• Solving Bernstein and Vazirani's problem with the 2-bit permutation function
• An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product
• A exact quantum learning algorithm for the 2-junta problem in constant time
• An exact quantum algorithm for the 2-junta problem
• Quantum algorithm for distribution-free junta testing
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Sample complexity of hidden subgroup problem
• Quantum learning Boolean linear functions w.r.t. product distributions
• An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
• Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
• An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
• Quantum algorithms for the Goldreich-Levin learning problem
• Learning bounds for quantum circuits in the agnostic setting
• Quantum property testing for bounded-degree graphs
• Quantum algorithms for testing properties of distributions
• Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
• scientific article; zbMATH DE number 6538684 (Why is no real title available?)
• Application of a generalization of Russo's formula to learning from multiple random oracles
• Efficient quantum algorithms for (gapped) group testing and junta testing
• Optimal quantum sample complexity of learning algorithms
• Quantum algorithms for testing and learning Boolean functions
• Testing juntas: a brief survey
• Quantum hardness of learning shallow classical circuits
• Two new results about quantum exact learning
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Quantum Algorithms for Testing Properties of Distributions
• scientific article; zbMATH DE number 7651037 (Why is no real title available?)
• Solving the learning parity with noise problem using quantum algorithms
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• An exact quantum logarithmic time algorithm for the 3-junta problem
• Learning low-degree quantum objects
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• Classical verification of quantum learning

This page was built for publication: Quantum algorithms for learning and testing juntas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2462663)