证明浅层量子电路在分布学习中存在无条件优势
An unconditional distribution learning advantage with shallow quantum circuits
- 用浅层量子电路（QNC^0）学习生成分布，优于经典电路（NC^0）
- 在特定分布学习任务中，量子电路表现显著更优，无需额外假设
- 适合关注量子优势理论与近中期量子计算应用的研究者
量子计算研究的核心挑战之一是能否在具有实际应用意义的近中期量子电路中发现量子优势。本文在概率近似正确（PAC）分布学习框架下，证明了浅层量子电路的无条件优势。我们识别出一个有意义的生成分布学习问题，其中仅使用单/双量子比特门的常数深度量子电路（QNC^0）在作为假设类时，优于常数深度有界扇入经典电路（NC^0）。由此，我们建立了浅层量子电路与浅层经典电路之间的PAC分布学习分离。该结果基于Bene Watts和Parham关于浅层电路采样任务的无条件量子优势研究，技术上将其提升至超平面学习问题，并揭示非局域相关性是量子优势的根源。
原文摘要 · Abstract (English)
One of the core challenges of research in quantum computing is concerned with the question whether quantum advantages can be found for near-term quantum circuits that have implications for practical applications. Motivated by this mindset, in this work, we prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses. We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC^0) are superior compared to constant-depth bounded fan-in classical circuits (NC^0) as a choice for hypothesis classes. We hence prove a PAC distribution learning separation for shallow quantum circuits over shallow classical circuits. We do so by building on recent results by Bene Watts and Parham on unconditional quantum advantages for sampling tasks with shallow circuits, which we technically uplift to a hyperplane learning problem, identifying non-local correlations as the origin of the quantum advantage.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。