Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

DOI10.1137/S0097539795293123zbMath0918.68033WikidataQ60307425 ScholiaQ60307425MaRDI QIDQ4229427

Nader H. Bshouty, Jeffrey C. Jackson

Publication date: 22 February 1999

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

zbMATH Keywords

Fourier transformquantum computingmachine learningdisjunctive normal form (DNF)quantum example oracle

Mathematics Subject Classification ID

Related Items (18)

Quantum machine learning: a classical perspective ⋮ 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 ⋮ Learning quantum finite automata with queries ⋮ An improved lower bound on query complexity for quantum PAC learning ⋮ Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices ⋮ Quantum algorithms for learning and testing juntas ⋮ Improved bounds on quantum learning algorithms ⋮ Unnamed Item ⋮ The geometry of quantum learning ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Unnamed Item ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Learning DNF from random walks ⋮ Quantum learning of concentrated Boolean functions ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound

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