Optimal Quantum Sample Complexity of Learning Algorithms

Srinivasan Arunachalam, Ronald de Wolf

In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its "richness." In the PAC model $$ Θ\Big(\frac{d}{\…