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

SIAM Journal on Computing

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

Nader H. Bshouty, Jeffrey C. Jackson

Published Jan 1, 1998• 87 citations
Publisher

Abstract

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.

DOI
10.1137/s0097539795293123

Related papers

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

Learning DNF over the uniform distribution using a quantum example oracle

Nader H. Bshouty, Jeffrey C. Jackson

We generalize the notion of PAC learning from an example oracle to a notion of efficient learning on

Conference on Learning Theory•Jan 1, 1995•36 citations

On the Quantum versus Classical Learnability of Discrete Distributions

Ryan Sweke, Jean‐Pierre Seifert, Dominik Hangleiter +1 more

Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete probability distributions which, under the decisional Diffie-Hellman assumption, is provably not efficiently PAC learnable by a classical generative modelling algorithm, but for which we construct an efficient quantum learner. This class of distributions therefore provides a concrete example of a generative modelling problem for which quantum learners exhibit a provable advantage over classical learning algorithms. In addition, we discuss techniques for proving classical generative modelling hardness results, as well as the relationship between the PAC learnability of Boolean functions and the PAC learnability of discrete probability distributions.

arXiv:2007.14451•Quantum•Mar 23, 2021•86 citations

Algorithmic models in quantum mechanics

Andrea Rocchetto

We study classical and quantum learning algorithms with access to data produced by a quantum process. First, we consider the problem of learning quantum states and, in the framework of the probably approximately correct (PAC) model, prove that stabiliser states are efficiently learnable. Second, we introduce a generative model based on artificial neural networks capable of finding efficient representations of quantum states and assess its performance on states with varying levels of complexity. Third, we discuss the time complexity of classical and quantum learning algorithms and prove that Boolean functions in disjunctive normal form are efficiently quantum PAC learnable under product distributions.

•Jan 1, 2019•0 citations

Quantum DNF Learnability Revisited

Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami

We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^{3}/ε+ s^{2}/ε^{2})$, where $s$ is the size of DNF formula and $ε$ is the PAC error accuracy. If $s$ and $1/ε$ are comparable, this gives a modest improvement over a previously known classical query complexity of $\tilde{O}(ns^{2}/ε^{2})$. We also show a lower bound of $Ω(s\log n/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF of size $s$ with $n$ inputs under the uniform distribution.

arXiv:quant-ph/0202066•Feb 12, 2002•0 citations

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Natsuto Isogai, Satoshi Yoshida, Mio Murao

Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.

quant-pharXiv:2609.38403•Oct 1, 2026•0 citations
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.
Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete probability distributions which, under the decisional Diffie-Hellman assumption, is provably not efficiently PAC learnable by a classical generative modelling algorithm, but for which we construct an efficient quantum learner. This class of distributions therefore provides a concrete example of a generative modelling problem for which quantum learners exhibit a provable advantage over classical learning algorithms. In addition, we discuss techniques for proving classical generative modelling hardness results, as well as the relationship between the PAC learnability of Boolean functions and the PAC learnability of discrete probability distributions.
We study classical and quantum learning algorithms with access to data produced by a quantum process. First, we consider the problem of learning quantum states and, in the framework of the probably approximately correct (PAC) model, prove that stabiliser states are efficiently learnable. Second, we introduce a generative model based on artificial neural networks capable of finding efficient representations of quantum states and assess its performance on states with varying levels of complexity. Third, we discuss the time complexity of classical and quantum learning algorithms and prove that Boolean functions in disjunctive normal form are efficiently quantum PAC learnable under product distributions.
We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of O~(s3/ε+s2/ε2)\tilde{O}(s^{3}/ε+ s^{2}/ε^{2})O~(s3/ε+s2/ε2), where sss is the size of DNF formula and εεε is the PAC error accuracy. If sss and 1/ε1/ε1/ε are comparable, this gives a modest improvement over a previously known classical query complexity of O~(ns2/ε2)\tilde{O}(ns^{2}/ε^{2})O~(ns2/ε2). We also show a lower bound of Ω(slog⁡n/n)Ω(s\log n/n)Ω(slogn/n) on the query complexity of any quantum PAC algorithm for learning a DNF of size sss with nnn inputs under the uniform distribution.
Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.