量子样本比经典样本更强大，可高效学习特定分布。
A Quantum/Classical Example Oracle Separation for Making Things Up
- 构建量子/经典样本的预言机分离，对比学习效率
- 在预言机下，量子样本可高效生成分布，经典样本不可
- 为量子优势提供新证据，适合量子机器学习研究者
我们研究了量子样本相对于经典样本在 PAC 学习框架中的能力。两个学习算法均具备量子计算能力，但一个仅能获取量子样本，另一个只能获取经典样本。此前未知是否存在仅靠后者无法高效完成的学习任务。本文主要结果是：相对于一个预言机，存在某些分布，量子学习者凭借量子样本可高效生成，而仅拥有经典样本的量子学习者则无法做到，为该问题的肯定回答提供了进展。
原文摘要 · Abstract (English)
We study the power of quantum examples, as compared to classical examples, in the PAC learning framework. Here, we have two learning algorithms, both with access to quantum computation, but one gets quantum examples, whereas the other gets classical examples. It was previously unknown whether there were learning tasks that can be efficiently performed but not by the latter. Our primary 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 examples, but not by a quantum learner with access to only classical examples, making progress to answering this question in the affirmative.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。