### Learning DNF over the Uniform Distribution Using a
Quantum Example Oracle

**Authors: Nader H. Bshouty and Jeffrey C. Jackson **

**Source: ***SIAM Journal on Computing* Vol. **28**, No. 3,
1999, 1136-1153.

**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.

©Copyright 1999, Society for Industrial and Applied Mathematics.