Learning DNF over the uniform distribution using a quantum example oracle

Abstract

We generalize the notion of 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 DNF is efficiently learnable with respect to the uniform dis-, tribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-leaxnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle. We also generalize the notion of classification noise to the quantum setting and show that the quantum DNF algorithm learns even in the presence of such noise. This result contrasts with a recent negative result for DNF in the statistical query model of learning from noisy data.