Learning DNFs under product distributions via μ-biased quantum Fourier sampling
This work provides an incremental extension to quantum learning theory by generalizing a prior result from uniform to product distributions.
The paper tackles the problem of learning DNF formulas under product distributions using a quantum example oracle, achieving polynomial-time quantum PAC learning, whereas the best classical algorithm without membership queries runs in superpolynomial time.
We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The best classical algorithm (without access to membership queries) 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.