Metraipolis › archive › dc_e95f55f3dd62

A Quantum/Classical Example Oracle Separation for Making Things Up — arXiv:2608.11648

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11648
License (as archived)
CC0-1.0
Archived
2026-10-19T05:40:18.409Z
SHA-256 of the archived text
574499fde9eafc5884344a894684d493959fbcc7f7c410b1187627e0b02a5be5
Stable URL of this page
https://metraipolis.com/documento/dc_e95f55f3dd62

How to cite

A Quantum/Classical Example Oracle Separation for Making Things Up — arXiv:2608.11648 — arXiv (en), https://arxiv.org/abs/2608.11648 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e95f55f3dd62 (Metraipolis archive dc_e95f55f3dd62, sha256 574499fde9eafc5884344a894684d493959fbcc7f7c410b1187627e0b02a5be5)
BibTeX
@misc{dce95f55f3dd62,
  title = {A Quantum/Classical Example Oracle Separation for Making Things Up — arXiv:2608.11648},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11648},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e95f55f3dd62; sha256 574499fde9eafc5884344a894684d493959fbcc7f7c410b1187627e0b02a5be5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11648. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-13 in cs.LG).
Categorie arXiv: Quantum Physics (quant-ph) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2608.11648 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:18:32.543Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).