A Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms

Daniel Z. Zanger

Using quantum algorithms, we obtain, for accuracy $\epsilon >0$ and confidence $1-\delta ,0<\delta <1,$ a new sample complexity upper bound of $O((\mbox{log}(\frac{1}δ))/ε)$ as $\epsilon ,\delta \to 0$ for…