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

Fourier transformmachine learningquantum computingdisjunctive normal form (DNF)quantum 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)

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

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)