Exponential quantum advantage in processing massive classical data

普适性量子优势——尤其是在经典数据处理与机器学习领域——长期以来一直是一个根本性的开放问题。本研究证明：一台规模仅为对数多项式量级的小型量子计算机，即可在海量经典数据上实时处理样本，完成大规模分类与降维任务；而任何达到同等预测性能的经典机器，其规模必须呈指数级增长。进一步地，那些虽为指数级规模、但仍低于该所需规模的经典机器，则需消耗超多项式倍数的样本量与运行时间，方能完成相同任务。我们在真实世界应用中验证了上述量子优势，包括单细胞RNA测序分析与电影评论情感分析，结果表明：仅需少于60个逻辑量子比特，即可实现设备规模缩减达四个至六个数量级。此类量子优势源于“量子预言机草图”（quantum oracle sketching）算法——该算法仅利用随机抽取的经典数据样本，即可使量子系统以叠加态方式访问经典世界。结合“经典阴影”（classical shadows）技术，我们的算法绕开了传统量子机器学习中固有的数据加载与读出瓶颈，从而直接从海量经典数据中构建出简洁高效的经典模型；而这一任务被严格证明：任何规模未达指数级放大的经典机器均无法完成。尤为重要的是，即使赋予经典机器无限运行时间，或即便复杂度类BPP与BQP相等（即经典计算机在多项式时间内可模拟任意量子计算），这些量子优势依然成立；其唯一依赖的前提，仅仅是量子力学本身的正确性。综上，我们的成果确立了“基于经典数据的机器学习”作为普适且自然的量子优势领域，同时也构成了在计算复杂性前沿上检验量子力学基本原理的一项根本性实验判据。

验证在经典数据处理和机器学习任务（如大规模分类与降维）中，是否存在严格、可证明的量子优势——即小规模量子计算机（polylog大小，<60逻辑比特）能否以指数级更低的硬件资源需求，实现与经典机器学习模型相当或更优的预测性能，且该优势不依赖于未被证实的复杂性假设（如BPP≠BQP），而仅基于量子力学基本原理。这是一个长期悬而未决的基础性问题，此前缺乏对经典数据上‘广泛适用’（broadly applicable）、‘实用规模’、‘可证明’量子优势的构造性证明。

提出‘量子预言机草图’（quantum oracle sketching）：一种无需显式量子随机存取存储器（QRAM）的数据接入范式，允许量子处理器仅通过随机采样的经典数据点，在量子叠加中高效构建数据结构；结合‘经典影子’（classical shadows）技术，实现对高维经典数据的低开销量子感知与 succinct classical model 提取。核心创新在于完全规避了传统量子机器学习中致命的‘数据加载瓶颈’和‘读出瓶颈’，使量子处理器能以O(polylog N)资源处理O(N)量级样本（N→∞），而任何非指数级增大的经典算法在样本复杂度和时间复杂度上均被严格证明为次优。

在真实世界任务中验证：单细胞RNA测序（10^5+基因×10^4细胞）和电影评论情感分析（IMDb级文本）；仅需<60逻辑量子比特即实现4–6个数量级的硬件规模压缩；理论证明经典对手即使拥有超多项式时间或无限时间，只要其尺寸未达指数级，就必然需要超多项式更多样本与运行时间；所有结论仅依赖量子力学正确性，不假设BPP≠BQP；论文未提及开源代码，但方法完全基于标准量子线路+经典后处理，具备可复现性；未来方向包括：噪声适应性实现、与NISQ设备对接、与联邦学习/隐私计算结合、以及向更大规模生物医学数据扩展。

Quantum Algorithmic Measurement for Classical Data (Huang et al., Nature Physics 2021); Predicting Many Properties of a Quantum System from Very Few Measurements (Huang, Kueng & Preskill, Nature Physics 2020); The Power of Quantum Fingerprinting (Buhrman et al., STOC 2001); Limitations of Quantum Advice and One-Way Communication (Aaronson, TCS 2005); No Classical Oracle Separation Between BQP and BPP (Chen et al., arXiv:2307.16088); Quantum Machine Learning in Feature Hilbert Spaces (Schuld & Petruccione, PRL 2021)