Quantum DNF Learnability Revisited

Maria Schuld, Francesco Petruccione

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.

Antonio Macaluso

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.

Pawan Whig, Pavika Sharma, Ahmad A. Elngar +1 more

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.