What type of study is this?

September 5, 2025Open Access

Quantum Learning Theory Beyond Batch Binary Classification

Key Points

Sample complexity in quantum learning matches classical approaches for multiclass learning, hence adapting traditional models is essential.
Extending previous results, findings reveal similarities between quantum and classical complexities across various learning settings, underscoring the relevance of quantum methods.
The investigation involves extending classical adversarial models to quantum scenarios, highlighting broader applications in adaptive learning contexts.
Implications of these findings reinforce the potential of quantum learning theories in improving algorithmic efficiency in complex, real-world tasks.

Abstract

Arunachalam and de Wolf (2018) arunachalam2018optimal showed that the sample complexity of quantum batch learning of boolean functions, in the realizable and agnostic settings, has the same form and order as the corresponding classical sample complexities. In this paper, we extend this, ostensibly surprising, message to batch multiclass learning, online boolean learning, and online multiclass learning. For our online learning results, we first consider an adaptive adversary variant of the classical model of Dawid and Tewari (2022) dawid2022learnability. Then, we introduce the first (to the best of our knowledge) model of online learning with quantum examples.

Quantum Learning Theory Beyond Batch Binary Classification

Key Points

Abstract

Cite This Study