量子算法在非均匀数据下学习周期神经元，实现指数级加速。
Quantum advantage for learning shallow neural networks with natural data distributions
- 设计高效量子算法学习周期神经元，适用于多种非均匀分布。
- 证明经典梯度算法和广义统计查询算法均难以解决该问题。
- 首次明确处理实值函数，展示指数级量子优势。
在缺乏大型量子计算机进行性能验证的情况下，量子统计查询（QSQ）模型是研究量子算法学习经典函数并探索机器学习中量子优势的主要理论工具。然而，我们对该模型中的量子优势理解仅限于两个极端：要么在均匀输入分布下存在指数级优势，要么在任意分布下无优势。本文通过设计一种在多种非均匀分布下学习周期神经元的高效量子算法，填补了这两类情形之间的空白，并首次对实值函数进行了明确分析。我们证明该问题不仅对经典的梯度算法（机器学习主流方法）难以求解，对更广泛的统计查询算法也具有困难性，从而建立了指数级量子优势。
原文摘要 · Abstract (English)
Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。