处理海量经典数据的指数级量子优势

arXiv:2604.07639v2 公告类型：替换交叉 摘要：广泛适用的量子优势，尤其是在经典数据处理和机器学习领域，一直是一个尚未解决的基础性问题。在本工作中，我们证明，一台规模仅为多对数级的小型量子计算机可以通过即时处理样本，在海量经典数据上执行大规模分类和降维；而任何要达到相同性能的经典机器都需要指数级更大的规模。此外，规模虽指数级大于量子机器、但仍低于所需规模的经典机器，需要超多项式倍的样本和时间。我们在包括单细胞 RNA 测序和影评情感分析在内的现实应用中，为这些量子优势提供了证据：使用少于 60 个逻辑量子比特，即可实现四至六个数量级的规模缩减。这些量子优势由 quantum oracle sketching 实现；这是一种仅使用随机经典数据样本、以量子叠加方式访问经典世界的算法。结合 classical shadows，我们的算法绕过了数据加载和读出瓶颈，能够从海量经典数据中构建简洁的经典模型；对于任何规模没有比量子机器大到指数级的经典机器而言，这项任务已被证明是不可能的。即使赋予经典机器无限时间，或即使 BPP = BQP，这些量子优势依然存在，并且仅依赖于量子力学的正确性。总而言之，我们的结果确立了经典数据上的机器学习是量子优势一个广泛且自然的领域，也是复杂性前沿检验量子力学的一项基础性测试。