Quantum algorithms for learning and testing juntas
From MaRDI portal
Publication:2462663
DOI10.1007/s11128-007-0061-6zbMath1155.81014arXiv0707.3479OpenAlexW3099022082MaRDI QIDQ2462663
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
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
