# A Quantum/Classical Example Oracle Separation for Making Things Up

arXiv: https://arxiv.org/abs/2608.11648 · HTML: https://mlsanity.com/paper/2608.11648/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Builds on (most cited first, 10 of 10)

- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Exponential separations between classical and quantum learners](https://mlsanity.com/paper/2306.16028/) (2023)
- [Improved machine learning algorithm for predicting ground state properties](https://mlsanity.com/paper/2301.13169/) (2023)
- [Quantum query complexity of entropy estimation](https://mlsanity.com/paper/1710.06025/) (2017)
- [Distributional property testing in a quantum world](https://mlsanity.com/paper/1902.00814/) (2019)
- [Breaking Symmetric Cryptosystems using Quantum Period Finding](https://mlsanity.com/paper/1602.05973/) (2016)
- [The Probably Approximately Correct Learning Model in Computational Learning Theory](https://mlsanity.com/paper/2511.08791/) (2025)
- [Conjugate queries can help](https://mlsanity.com/paper/2510.07622/) (2025)

## Abstract (arXiv)

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 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.