A Quantum/Classical Example Oracle Separation for Making Things Up
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.11648
curl -X POST /api/v1/records/arxiv/2608.11648/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.11648/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'