PreprintCC BY 4.0arXiv
A Quantum/Classical Example Oracle Separation for Making Things Up
Abstract
Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.
Related
- An example of universal braiding in Links--Gould topological quantum computation
- Quantum Graph Theory by Example
- Universal classical and quantum fluctuations in the large deviations of current of noisy quantum systems: Quantum symmetric simple exclusion and inclusion processes
- Quantum-classical dynamics of Rashba spin-orbit coupling
- Classical and Quantum Logics with Multiple Non-Equivalent and Non-Isomorphic Models
BibTeX
@misc{chen2026quantumclassical,
title = {{A Quantum/Classical Example Oracle Separation for Making Things Up}},
author = {Kenny Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.11648},
eprint = {2608.11648},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.11648},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Quantum/Classical Example Oracle Separation for Making Things Up
AU - Kenny Chen
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2608.11648
UR - https://arxiv.org/abs/2608.11648
AB - Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.
ER -