第一次有人证明量子优化赢在哪儿
量子计算领域最贵的一句话是优势（advantage）。过去二十年，这句话被用在太多地方，又被证伪得太快。DQI 这个框架出来的时候，理论物理学家自己就把它当成了一个问句：它能不能真的可证明地打败所有多项式时间经典算法。
第一次有人证明量子优化赢在哪儿
量子计算领域最贵的一句话是优势（advantage）。过去二十年，这句话被用在太多地方，又被证伪得太快。DQI 这个框架出来的时候，理论物理学家自己就把它当成了一个问句：它能不能真的可证明地打败所有多项式时间经典算法。
10 月 1 日下午五点四十八秒，Freie Universität Berlin 的五个人把答案交上来了。Maximilian J. Kramer，Elies Gil-Fuster，Benjamin D. M. Jones，Jens Eisert，Franz J. Schreiber。59 页，3 张图，arXiv:2610.02145。
答案是在 oracle 设定下给的，这是必须先说清的前提。
折起来的多项式相交
被优化的任务叫 folded optimal polynomial intersection。设定是：接受集随机选出来，只能通过成员查询访问。
用一句大白话讲这个设定有多干净：你不许看输入长什么样，你只能一个一个去问某个东西在不在集合里。所有信息都要花查询次数去换。
DQI 的框架在量子这边本来就有强性能保证，它靠的是优化与编码理论之间一个成熟的二元性。这篇的工作是把 Yamakawa 与 Zhandry 那个精确搜索 oracle 分离用的经典下界方法，从精确搜索推到近似情形。
三个数字
论文给的具体例子是码率 0.3。
| 方案 | 期望分数 | 性质 |
|---|---|---|
| DQI 算法 | 约 0.85 | 量子 |
| 修正后的 DQI 算法 | 约 0.95 | 量子，差距更大 |
| 经典算法阈值 | 0.65 | 超过任意固定量即需超多项式次成员查询 |
补上量级锚点。0.95 减 0.65 是 0.30。0.85 减 0.65 是 0.20。
修正是靠 Sun 与 Wootters、Horinaga 与 Yamakawa、Jo 的近期进展做的，论文明确说是构建在这些工作之上。这三项工作本身是近两年出来的，DQI 从提出到拿到这个分离只走了很短的路。
这个证明的重量在哪
三点需要在正确的层级上理解。
第一，这是可证明性，不是实验演示。 论文里没有一个量子比特，也没有任何硬件。全篇是数学。标题里的 quantum advantage 在字面上成立，但它证明的是存在一个分离，不是任何一台机器跑得更快。
第二，问题的构造性。 folded OPI 是特意造出来的任务，接受集随机选、只能成员访问。Schreiber 与 Eisert 都在 Fraunhofer Heinrich Hertz Institute 与自由大学，这是理论物理的班底。论文自己在结论里留了口子，作者建议进一步探索把这些结果推到精心构造的数学问题之外，摘要并没有给出具体的下一步计划。
第三，oracle 设定降低了门槛。 经典下界在成员查询模型里成立，绕开了访问输入结构的任何可能性。这让分离更容易证明，也让离真实应用更远。
| 三个层级 | 这次做到了哪一层 |
|---|---|
| 可证明分离（oracle 设定） | 做到了，folded OPI 上严格间隔 |
| 真实问题上的分离 | 未做，构造问题 |
| 实验演示优势 | 未做，理论论文 |
【判断】把它放在时间线上看更清楚。2024 年 Google Willow 的随机线路采样演示，给出的是实验上可测的采样优势；同期 Quantinuum 与 Google 的 40 个逻辑比特交叉验证，走的是相干性路线。这些都要求硬件。DQI 这条线是另一件事，它在硬件出现之前就把分离钉在纸面上，为的是当硬件足够时，理论上已经知道该往哪走。
【直引】作者在摘要里用的措辞是，在 oracle 设定下建立这种优势，承认测试任务是折叠后的最优多项式相交，接受集随机选并通过成员 oracle 访问。
有一条线值得对照
同一天，另一组人 Licheng Li 与 Chunhao Wang 交了一篇东西，是同期的另一个量子复杂度结果（2610.02030）。他们在稀疏厄米哈密顿量模拟上给出了对最大列欧几里得范数（记作 H 的 1 到 2 范数）的最优依赖，去掉了 Low 算法（STOC 2019）里的次多项式开销，换成加性对数精度项。
这篇顺手解决了一个开放问题。Berry 与 Childs 在 2012 年的 QIC 论文里提出黑箱酉矩阵实现的开放问题，这篇给出任意 N 乘 N 酉矩阵在常数误差下需要 Theta(根号 N) 次查询的界，是最优的。
两篇都在 10 月 1 日挂出，都属 quant-ph。一篇说量子能赢在哪儿，一篇说经典模拟的代价到底该怎么算。
【推论】把这两篇并起来看，量子算法研究的一个阶段特征很清楚：十年前争的是有没有分离，现在争的是分离的形状能不能被写进具体复杂度类，以及最优界能不能落地。2026 年 10 月这两篇给出的都是形式化结果，没有一台机器参与。这不是退步，是把问题问准了。
三处待确认
- arXiv v1 为预印本，59 页，未经同行评审
- oracle 模型里经典下界依赖成员查询计数，真实模型里对应的是哪一种成本假设，论文未展开
- 论文摘要未给具体的码率-分数曲线，0.85 与 0.95 是码率 0.3 这一个点
参考来源
- arXiv:2610.02145，Kramer, Gil-Fuster, Jones, Eisert, Schreiber，2026-10-01 提交，59 页 3 图
- arXiv:2610.02030，Licheng Li, Chunhao Wang，2026-10-01 提交
- Quantum Zeitgeist 对 DQI 分离的报道