Quantum algorithms for learning and testing juntas

DOI10.1007/s11128-007-0061-6zbMath1155.81014arXiv0707.3479OpenAlexW3099022082MaRDI QIDQ2462663

Rocco A. Servedio, Alp Atıcı

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 theoryquantum algorithmjuntaFourier samplequantum property testing

Mathematics Subject Classification ID

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

Related Items (22)

Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm ⋮ A exact quantum learning algorithm for the 2-junta problem in constant time ⋮ 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 Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product ⋮ Learning bounds for quantum circuits in the agnostic setting ⋮ Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles ⋮ An exact quantum algorithm for the 2-junta problem ⋮ Quantum algorithms for testing and learning Boolean functions ⋮ Testing Juntas: A Brief Survey ⋮ Unnamed Item ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ 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 ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound ⋮ An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product

Cites Work

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

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