# Learning DNFs under product distributions via μ-biased quantum Fourier sampling

arXiv: https://arxiv.org/abs/1802.05690 · HTML: https://mlsanity.com/paper/1802.05690/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)

## Abstract (arXiv)

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.