Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Learning Theory

Learning DNF over the uniform distribution using a quantum example oracle

Nader H. Bshouty, Jeffrey C. Jackson

Published Jan 1, 1995• 36 citations
Publisher

Abstract

We generalize the notion of PAC learning from an example oracle to a notion of efficient learning on
DOI
10.1145/225298.225312

Related papers

A Quantum/Classical Example Oracle Separation for Making Things Up

Kenny Chen

Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.

quant-pharXiv:2608.11648•Aug 13, 2026•0 citations

Quantum Harmonic Sieve: Learning DNF with a Classical Example Oracle

Dan A. Ventura, Tony R. Martinez

This paper has been withdrawn by the authors due to a problem with *efficiently* predicting the large fourier coefficients. It is being reworked and will be resubmitted in the near future.

arXiv:quant-ph/9805043•May 15, 1998•0 citations

An improved lower bound on query complexity for quantum PAC learning

Chi Zhang

Information Processing Letters•Oct 13, 2010•17 citations

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

Nader H. Bshouty, Jeffrey C. Jackson

We generalize the notion of probably approximately correct (PAC) learning from an example oracle to a notion of efficient learning on a quantum computer using a quantum example oracle. This quantum example oracle is a natural extension of the traditional PAC example oracle, and it immediately follows that all PAC-learnable function classes are learnable in the quantum model. Furthermore, we obtain positive quantum learning results for classes that are not known to be PAC learnable. Specifically, we show that disjunctive normal form (DNF) is efficiently learnable with respect to the uniform distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle.

SIAM Journal on Computing•Jan 1, 1998•87 citations

Learning DNFs under product distributions via mu--biased quantum Fourier sampling

Varun Kanade, Andrea Rocchetto, Simone Severini B

We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The current best classical algorithm runs in superpolynomial time. Our result extends the work by Bshouty and Jackson (1998) that proved that DNF formulae are efficiently learnable under the uniform distribution using a quantum example oracle. Our proof is based on a new quantum algorithm that efficiently samples the coefficients of a μ–biased Fourier transform.

arXiv:1802.05690•Quantum Information and Computation•Dec 1, 2019•10 citations

Quantum DNF Learnability Revisited

Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami

Lecture notes in computer science•Jan 1, 2002•5 citations
Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.
We generalize the notion of probably approximately correct (PAC) learning from an example oracle to a notion of efficient learning on a quantum computer using a quantum example oracle. This quantum example oracle is a natural extension of the traditional PAC example oracle, and it immediately follows that all PAC-learnable function classes are learnable in the quantum model. Furthermore, we obtain positive quantum learning results for classes that are not known to be PAC learnable. Specifically, we show that disjunctive normal form (DNF) is efficiently learnable with respect to the uniform distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle.