arXiv：cs.LG（机器学习，全量分类）· Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod R. McClean, Hsin-Yuan Huang·· 15 小时前AI 评分69
arXiv 论文证明小型量子计算机处理大规模经典数据具有指数级优势
Exponential quantum advantage in processing massive classical data
AI 导读
arXiv 论文（arXiv:2604.07639）证明 polylog 规模的小型量子计算机可对大规模经典数据进行分类和降维，而达到相同预测性能的经典机器需要指数级更大的规模。
正文
Abstract:Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We provide evidence for these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP = BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.
| Comments: | 169 pages, including 10 pages of main text and 13 figures. Code available at this https URL |
| Subjects: | Quantum Physics (quant-ph); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Information Theory (cs.IT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2604.07639 [quant-ph] |
| (or arXiv:2604.07639v2 [quant-ph] for this version) | |
| https://doi.org/10.48550/arXiv.2604.07639 arXiv-issued DOI via DataCite |
Submission history
From: Haimeng Zhao [view email]
[v1]
Wed, 8 Apr 2026 22:55:59 UTC (6,009 KB)
[v2]
Thu, 1 Oct 2026 17:14:21 UTC (5,851 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org