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 distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, the quantum example oracle is provably 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. Quantum computation, Computational learning theory DNF, (Disjunctive normal form), Quantum example oracle, Classification noise, Statistical query learning
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1994
- Accession Number
- ADA286143
Entities
People
- Jeffrey Jackson
- Nader H. Bshouty
Organizations
- Carnegie Mellon University