Second QCOW Colloquium: Quantum Learning Theory

Learning theory has been a transformative force in modern computer science; its conceptual and mathematical tools - from the foundations of PAC learning and VC dimension to boosting, compression, generalization bounds - have reshaped algorithms, complexity theory, and statistics. By clarifying what can be learned, with how many samples, and at what computational cost, learning theory has provided a rigorous language for understanding data-driven computation.

Quantum Learning Theory is a rapidly developing area at the frontier of quantum computing and theoretical machine learning. It investigates the learnability of classical and quantum concepts under quantum access models, the sample and query complexity of quantum learners, and fundamental separations between classical and quantum learning paradigms. At the same time, it addresses questions motivated by physics: how efficiently can we predict properties of complex quantum systems, and how does quantum information alter the principles of inference and generalization? This way, beyond improved algorithms, Quantum Learning Theory searches for a structural understanding of learnability in the presence of quantum resources: Which foundations of classical learning theory admit robust quantum analogues, and where do these exhibit fundamentally new behaviour? What are the boundaries between classical and quantum learnability? Where do provable separations arise, and what structural features drive them? By studying these questions, the field builds strong bridges between theoretical computer science, computational learning theory, quantum algorithms, complexity theory, information theory, and quantum physics.