Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

DOI10.1137/S0097539795293123MaRDI QIDQ4229427zbMATH OpenWikidataFDO

Authors Nader H. Bshouty, Jeffrey Jackson

Publication date 22 February 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539795293123

zbMATH Keywords

disjunctive normal form (DNF)Fourier transformmachine learningquantum computingquantum example oracle

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 2090015
• Improved bounds on quantum learning algorithms
• Equivalences and Separations Between Quantum and Classical Learnability
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• Optimal quantum sample complexity of learning algorithms

Cited in

(23)

• An improved lower bound on query complexity for quantum PAC learning
• Quantum learning of concentrated Boolean functions
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Quantum algorithms for learning and testing juntas
• Improved bounds on quantum learning algorithms
• Learning DNF from random walks
• Sample complexity of hidden subgroup problem
• Quantum learning Boolean linear functions w.r.t. product distributions
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• Learning bounds for quantum circuits in the agnostic setting
• Quantum machine learning: a classical perspective
• Optimal quantum sample complexity of learning algorithms
• Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices
• scientific article; zbMATH DE number 2090015 (Why is no real title available?)
• Quantum hardness of learning shallow classical circuits
• Quantum Algorithms for Classical Probability Distributions
• Two new results about quantum exact learning
• Learning quantum finite automata with queries
• Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• Classical verification of quantum learning
• Tunable quantum neural networks in the QPAC-learning framework
• The geometry of quantum learning

This page was built for publication: Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

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