Quantum Learning Theory Beyond Batch Binary Classification

Preetham Mohan; Ambuj Tewari

doi:10.22331/q-2025-07-29-1813

Quantum Learning Theory Beyond Batch Binary Classification

¹Department of Mathematics, University of Michigan
²Department of Statistics, University of Michigan
³Department of Electrical Engineering and Computer Science, University of Michigan

Published:	2025-07-29, volume 9, page 1813
Editor:	Tongyang Li
Eprint:	arXiv:2302.07409v5
Doi:	https://doi.org/10.22331/q-2025-07-29-1813
Citation:	Quantum 9, 1813 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Arunachalam and de Wolf (2018) [1] showed that the sample complexity of quantum batch learning of boolean functions, in the realizable and agnostic settings, has the $\textit{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) [2]. Then, we introduce the first (to the best of our knowledge) model of online learning with quantum examples.

Featured image: A quantum circuit that transforms a quantum binary example $|\psi \rangle_{\bar{\mathcal{A}}}$ into a quantum multiclass example $|\psi \rangle_{\mathcal{A}}$, enabling a reduction-based proof of the quantum multiclass sample complexity lower bound in the batch setting.

A poster (presented at QIP 2024) is hosted at the following GitHub permalink.

Popular summary

Can quantum computers learn more efficiently than classical ones? This is a central question in quantum machine learning. A major hope has been that quantum computers might require far less data to identify patterns, especially in complex settings. However, recent research suggests that this advantage may be more limited than perhaps envisioned. In particular, earlier work showed that for simple yes/no (binary) classification tasks, quantum and classical learners require roughly similar amounts of data to succeed.

In this paper, we extend this finding to broader learning scenarios. We demonstrate that even for more complex tasks, such as choosing among many possible labels (multiclass learning) and learning in real time as data arrives (online learning), quantum learners do not learn from significantly fewer examples as compared to classical learners. In short, our work provides further theoretical evidence that, in terms of sample efficiency, quantum learning may not offer dramatic improvements in general settings. Understanding the specific cases in which quantum speedups do arise remains an important challenge.

► BibTeX data

@article{Mohan2025quantumlearning,
  doi = {10.22331/q-2025-07-29-1813},
  url = {https://doi.org/10.22331/q-2025-07-29-1813},
  title = {Quantum {L}earning {T}heory {B}eyond {B}atch {B}inary {C}lassification},
  author = {Mohan, Preetham and Tewari, Ambuj},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1813},
  month = jul,
  year = {2025}
}

► References

[1] Srinivasan Arunachalam and Ronald de Wolf. ``Optimal Quantum Sample Complexity of Learning Algorithms''. Journal of Machine Learning Research 19, 1–36 (2018). url: jmlr.org/papers/v19/18-195.html.
http://jmlr.org/papers/v19/18-195.html

[2] Philip Dawid and Ambuj Tewari. ``On Learnability under General Stochastic Processes''. Harvard Data Science Review 4 (2022).
https://doi.org/10.1162/99608f92.dec7d780

[3] Nader H. Bshouty and Jeffrey C. Jackson. ``Learning DNF over the uniform distribution using a quantum example oracle''. In Proceedings of the 8th Conference on Computational Learning Theory (COLT). Pages 118–127. ACM (1995).
https://doi.org/10.1145/225298.225312

[4] Rocco A. Servedio and Steven J. Gortler. ``Equivalences and Separations Between Quantum and Classical Learnability''. SIAM Journal on Computing 33, 1067–1092 (2004).
https://doi.org/10.1137/S0097539704412910

[5] Alp Atıcı and Rocco A. Servedio. ``Improved Bounds on Quantum Learning Algorithms''. Quantum Information Processing 4, 355–386 (2005).
https://doi.org/10.1007/s11128-005-0001-2

[6] Chi Zhang. ``An improved lower bound on query complexity for quantum PAC learning''. Information Processing Letters 111, 40–45 (2010).
https://doi.org/10.1016/j.ipl.2010.10.007

[7] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. ``Multiclass Learnability and the ERM Principle''. Journal of Machine Learning Research 16, 2377–2404 (2015). url: jmlr.org/papers/v16/daniely15a.html.
http://jmlr.org/papers/v16/daniely15a.html

[8] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. ``A Characterization of Multiclass Learnability''. In Proceedings of the 63rd Symposium on Foundations of Computer Science (FOCS). Pages 943–955. IEEE (2022). arXiv:2203.01550.
https://doi.org/10.1109/FOCS54457.2022.00093
arXiv:2203.01550

[9] Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. ``Multiclass Online Learning and Uniform Convergence''. In Proceedings of 36th Conference on Learning Theory (COLT). Pages 5682–5696. PMLR (2023). url: proceedings.mlr.press/v195/hanneke23b.html.
https://proceedings.mlr.press/v195/hanneke23b.html

[10] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. ``Learnability and the Vapnik-Chervonenkis dimension''. Journal of the ACM 36, 929–965 (1989).
https://doi.org/10.1145/76359.76371

[11] Steve Hanneke. ``The Optimal Sample Complexity of PAC Learning''. Journal of Machine Learning Research 17, 1–15 (2016). url: jmlr.org/papers/v17/15-389.html.
http://jmlr.org/papers/v17/15-389.html

[12] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. ``Toward efficient agnostic learning''. In Proceedings of the 5th Workshop on Computational Learning Theory (COLT). Pages 341–352. ACM (1992).
https://doi.org/10.1145/130385.130424

[13] Michel Talagrand. ``Sharper Bounds for Gaussian and Empirical Processes''. The Annals of Probability 22, 28–76 (1994).
https://doi.org/10.1214/aop/1176988847

[14] Balas K. Natarajan. ``On Learning Sets and Functions''. Machine Learning 4, 67–97 (1989).
https://doi.org/10.1007/BF00114804

[15] Shai Ben-David, Nicolo Cesa-Bianchi, David Haussler, and Philip M. Long. ``Characterizations of Learnability for Classes of $\{0,..., n\}$-Valued Functions''. Journal of Computer and System Sciences 50, 74–86 (1995).
https://doi.org/10.1006/jcss.1995.1008

[16] Nick Littlestone. ``Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm''. Machine Learning 2, 285–318 (1988).
https://doi.org/10.1023/A:1022869011914

[17] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. ``Agnostic Online Learning''. In Proceedings of the 22nd Conference on Learning Theory (COLT). (2009). url: api.semanticscholar.org/bendavid09agnostic.
https://api.semanticscholar.org/CorpusID:9403043

[18] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. ``Adversarial Laws of Large Numbers and Optimal Regret in Online Classification''. In Proceedings of the 53rd ACM SIGACT Symposium on Theory of Computing (STOC). Pages 447–455. ACM (2021). arXiv:2101.09054.
https://doi.org/10.1145/3406325.3451041
arXiv:2101.09054

[19] Anurag Anshu and Srinivasan Arunachalam. ``A survey on the complexity of learning quantum states''. Nature Reviews Physics 6, 59–69 (2024).
https://doi.org/10.1038/s42254-023-00662-4

[20] Srinivasan Arunachalam and Ronald de Wolf. ``Guest Column: A Survey of Quantum Learning Theory''. ACM SIGACT News 48, 41–67 (2017).
https://doi.org/10.1145/3106700.3106710

[21] Wilfred Salmon, Sergii Strelchuk, and Tom Gur. ``Provable Advantage in Quantum PAC Learning''. In Proceedings of the 37th Conference on Learning Theory (COLT). Pages 4487–4510. PMLR (2024). url: proceedings.mlr.press/v247/salmon24a.html.
https://proceedings.mlr.press/v247/salmon24a.html

[22] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. ``Quantum Coupon Collector''. In Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC). Pages 10:1–10:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020).
https://doi.org/10.4230/LIPIcs.TQC.2020.10

[23] Ashwin Nayak and Pulkit Sinha. ``Proper vs Improper Quantum PAC Learning'' (2024). arXiv:2403.03295.
arXiv:2403.03295

[24] Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. ``Proper Learning, Helly Number, and an Optimal SVM Bound''. In Proceedings of the 33rd Conference on Learning Theory (COLT). Pages 582–609. PMLR (2020). url: proceedings.mlr.press/v125/bousquet20a.html.
https://proceedings.mlr.press/v125/bousquet20a.html

[25] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. ``Smoothed Analysis of Online and Differentially Private Learning''. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS). Pages 9203–9215. Curran Associates, Inc. (2020). url: proceedings.neurips.cc/haghtalab20smoothed.
https://proceedings.neurips.cc/paper_files/paper/2020/hash/685bfde03eb646c27ed565881917c71c-Abstract.html

[26] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. ``Smoothed Online Learning is as Easy as Statistical Learning''. In Proceedings of the 35th Conference on Learning Theory (COLT). Pages 1716–1786. PMLR (2022). url: proceedings.mlr.press/v178/block22a.html.
https://proceedings.mlr.press/v178/block22a.html

[27] Gábor Lugosi and Gergely Neu. ``Online-to-PAC Conversions: Generalization Bounds via Regret Analysis'' (2024). arXiv:2305.19674.
arXiv:2305.19674

[28] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information: 10th Anniversary Edition''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667

[29] Leslie G. Valiant. ``A Theory of the Learnable''. Communications of the ACM 27, 1134–1142 (1984).
https://doi.org/10.1145/1968.1972

[30] Shima Bab Hadiashar, Ashwin Nayak, and Pulkit Sinha. ``Optimal Lower Bounds for Quantum Learning via Information Theory''. IEEE Transactions on Information Theory 70, 1876–1896 (2024).
https://doi.org/10.1109/TIT.2023.3324527

[31] Amit Daniely and Shai Shalev-Shwartz. ``Optimal Learners for Multiclass Problems''. In Proceedings of the 27th Conference on Learning Theory (COLT). Pages 287–316. PMLR (2014). url: proceedings.mlr.press/v35/daniely14b.html.
https://proceedings.mlr.press/v35/daniely14b.html

[32] Shai Shalev-Shwartz and Shai Ben-David. ``Understanding Machine Learning: From Theory to Algorithms''. Cambridge University Press. (2014).
https://doi.org/10.1017/CBO9781107298019

[33] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. ``Contextual Bandit Algorithms with Supervised Learning Guarantees''. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS). Pages 19–26. PMLR (2011). url: proceedings.mlr.press/v15/beygelzimer11a.html.
https://proceedings.mlr.press/v15/beygelzimer11a.html

[34] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. ``Sequential complexities and uniform martingale laws of large numbers''. Probability Theory and Related Fields 161, 111–153 (2015).
https://doi.org/10.1007/s00440-013-0545-5

[35] Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. ``Online learning of quantum states''. Journal of Statistical Mechanics: Theory and Experiment 2019, 124019 (2019).
https://doi.org/10.1088/1742-5468/ab3988

[36] Yihui Quek, Srinivasan Arunachalam, and John A Smolin. ``Private learning implies quantum stability''. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NeurIPS). Pages 20503–20515. (2021). url: openreview.net/quek21private.
https://openreview.net/forum?id=9XAxGtK5cdN

Cited by

[1] Steve Hanneke, Vinod Raman, Amirreza Shaeiri, and Unique Subedi, "Multiclass Transductive Online Learning", arXiv:2411.01634, (2024).

[2] Sagnik Chatterjee, "The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)", arXiv:2602.01054, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-17 19:15:21). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-17 19:15:19).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.