Quantum DNF Learnability Revisited

Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami

We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^3/\epsilon +s^2/{\epsilon }^2)$, where $s$ is the size of…