Learning DNFs under product distributions via μ-biased quantum Fourier sampling
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 efficient...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Rinton Press
2019
|