A brief history of quantum vs classical computational advantage

本综述文章全面总结了所有声称实现量子计算优势的实验，批判性地审视了它们所面临的挑战与反驳，探讨了特定问题中的理论优势，并强调了量子纠错方面的最新进展作为实现肖尔算法优势的关键步骤。

要点

以下是 Ryan LaRose 所著论文《量子计算优势与经典计算优势简史》的解读，已转化为通俗易懂的日常语言，并辅以富有创意的类比。

宏观图景：伟大的竞赛

想象一场两名选手之间的赛跑：经典计算机（我们当今使用的超级快速、可靠的马拉松选手）与量子计算机（基于量子物理奇特规则运行的神秘、闪电般的短跑选手）。

这篇论文的目标是记录每一次“量子短跑选手”宣称“我能比经典选手更快地解决这个特定谜题”时的比分。作者 Ryan LaRose 扮演体育历史学家的角色，回顾每一场比赛、每一次抗议和每一次取消资格，告诉我们这场比赛目前的准确态势。

论文将“优势”简单定义为：谁先完成任务？ 无论任务是否有用（如治愈疾病）还是仅仅是一个愚蠢的谜题，唯一的问题就是速度。

---

第一部分：“愚蠢谜题”类竞赛（实验性优势）

到目前为止，量子短跑选手尝试赢得三种特定类型的“愚蠢”竞赛。这些竞赛目前对建造桥梁或撰写电子邮件毫无用处；它们被专门设计为对经典计算机来说很难，但对量子计算机来说却很容易。

1. 随机电路采样竞赛（“抛硬币”混沌）

• 任务： 想象一台机器以完全随机、混乱的方式同时抛掷 53 枚硬币。量子计算机执行此操作并记录正反面模式。经典计算机必须猜测该模式会是什么。
• 首次胜利（谷歌，2019 年）： 谷歌的"Sycamore"计算机在 200 秒内完成了这项任务。他们声称，经典超级计算机完成同样的数学运算需要 10,000 年。
• 反击： 经典选手没有放弃。他们发明了新的、更聪明的方法来解决这个谜题。
  • 类比： 想象经典选手意识到他们不需要跑完整个赛道；他们可以通过发现的一条隧道走捷径。
  • 结果： 随着时间的推移，经典计算机变得更快。到 2024 年，一台经典超级计算机成功在86 秒内完成了同样的任务，击败了量子计算机。
• 裁决： 谷歌的首次胜利被“驳斥”了。经典选手赶了上来并超过了他们。然而，谷歌尝试了更大、更难的谜题（更多的硬币、更多的翻转），这些新比赛目前尚未被驳斥。

2. 高斯玻色采样竞赛（“光子弹球”）

• 任务： 这次竞赛不使用硬币，而是使用光粒子（光子）在镜子迷宫中弹跳。量子计算机将它们射入，它们落在特定位置。经典计算机必须计算它们落在哪里。
• 竞争者： 来自中国（USTC）和加拿大（Xanadu）的团队建造了这些基于光的赛车。
• 反击： 就像硬币竞赛一样，经典计算机发现了“漏洞”。他们意识到，如果光粒子不完美（它们确实从不完美），数学计算就会变得更容易。他们构建了新的算法，以比预期快得多的速度模拟光迷宫。
• 裁决： 这些主张大多被“弱驳斥”。这意味着经典计算机尚未在最大的谜题上击败量子计算机，但它们已经足够接近，以至于未来稍好一点的经典计算机很可能就能做到。

3. 量子模拟竞赛（“天气预报”）

• 任务： 模拟复杂系统（如磁性材料）随时间的变化。
• 竞争者： IBM 和 D-Wave。
• 反击： IBM 声称他们模拟磁性系统的速度快于经典计算机。但在两周内，经典研究人员表明，他们可以在笔记本电脑上在几分钟内完成同样的模拟。
• 裁决： IBM 的主张很快被“驳斥”。经典选手找到了一条更快的路线。D-Wave 最近的尝试仍在被观察中，但它可能会面临类似的挑战。

---

第二部分：“理论”类竞赛（数学证明）

有时，数学家会说：“如果我们建造一台完美的量子计算机，它应该能赢得这场比赛。”但历史表明，经典数学家非常擅长发现新技巧。

• 推荐系统竞赛： 有人提出了一种量子算法，声称能比任何经典计算机更快地向你推荐电影。
  • 转折： 一位经典数学家（Ewin Tang）意识到：“嘿，如果我们给经典计算机与量子计算机使用的相同特殊数据结构，它也能以同样的速度解决这个问题！”
  • 结果： 量子优势消失了。这被称为“去量子化”。
• 优化竞赛： 类似的故事也发生在旨在解决复杂调度问题的算法上。量子优势被宣称，随后发现了一种同样优秀的经典算法。

---

第三部分：最终疆域（纠错）

这里是论文最重要的结论：量子计算机是脆弱的。

• 类比： 想象量子短跑选手是一个玻璃人。他们速度快得惊人，但如果被一颗小石子（噪声）绊倒，他们就会粉碎。为了跑马拉松（例如分解大数以破解加密），他们需要穿上盔甲。
• 盔甲： 这副盔甲被称为量子纠错。它利用许多物理“玻璃”量子比特来创建一个坚固的“逻辑”量子比特。
• 当前状态： 我们刚刚开始建造这副盔甲。
  • 2024 年，谷歌宣布了一款新芯片（Willow），其中的“逻辑”量子比特（装甲版）比单个“物理”量子比特（玻璃版）持续的时间更长。
  • 这是“圣杯”时刻。它证明了增加部件来纠正错误实际上使系统变得更好，而不是更糟。
• 未来： 在拥有这副盔甲之前，我们无法进行“有用”的竞赛（如破解代码或模拟新药物）。论文认为，纠错是量子计算机真正在现实世界问题上击败经典计算机之前的最后一道疆域。

总结：我们处于什么位置？

论文得出结论，这场竞赛是一场拔河。

1. 量子计算机取得重大飞跃。
2. 经典计算机变得更聪明，找到捷径，并赶上（或超过）他们。
3. 量子计算机构建更好的硬件并再次尝试。

目前，我们处于边界上。我们已经看到量子计算机在特定的、无用的谜题上获胜，但经典计算机已经找到了击败它们几乎所有方法。论文指出，为了让量子计算机赢得一场有用的竞赛，它们必须首先掌握纠错的艺术。在此之前，领先地位将不断易手。

技术摘要

标题： 量子计算优势与经典计算优势的简要历史
作者： Ryan LaRose
来源： Quantum（2026-05-14 录用）

问题陈述

本文探讨了“量子计算优势”（亦称为量子霸权或超越经典计算）不断演变的格局。核心问题在于定义并追踪经典计算机与量子计算机之间计算可行性的动态边界。作者将计算优势具体定义为：针对特定问题，无论其实际效用如何，在求解时间上的减少。本综述旨在编目迄今为止所有关于量子优势的实验声明，以及随后出现的经典挑战、反驳和改变这些声明状态的理论进展。

方法论

本文采用全面的综述方法，综合了实验物理学、计算机科学和复杂性理论的历史数据。

1. 按时间顺序编目： 作者编制了所有声称实现量子优势的实验时间线，并按问题类型进行分类：随机电路采样（RCS）、高斯玻色采样（GBS）和量子模拟（QSim）。
2. 状态分类： 根据后续文献，为每个实验分配状态：
   • 未反驳： 尚无经典算法能以更快的速度模拟该实验。
   • 受挑战： 经典算法已缩短模拟时间，或质疑了实验的特定方面。
   • 弱反驳： 存在一种经典算法，很可能能在近期的经典硬件上模拟该实验。
   • 已反驳： 经典计算机已成功以快于量子设备的速度模拟了该实验。
3. 理论分析： 综述考察了特定领域（近似优化、推荐系统、量子化学）的理论优势，以突显“去量子化”（即受量子算法启发而开发的经典算法）如何侵蚀理论上的加速优势。
4. 纠错综述： 本文追溯了量子纠错（QEC）实验的历史，将其确定为在如肖尔算法等需要容错性的算法中实现优势的必要的“最后疆域”。

主要贡献

• 综合状态表： 本文提供了表 1，按时间顺序列出了所有量子优势声明（从谷歌 2019 年的 Sycamore 到 D-Wave 2024 年的模拟）及其当前关于经典反驳的立场。
• 挑战的详细叙述： 本文记录了量子实验与经典模拟之间的“军备竞赛”。显著的贡献包括追踪张量网络收缩优化（例如“大头”算法、超图划分）和噪声利用策略，这些策略已将特定实验的估计经典运行时间从数千年减少至数小时甚至数秒。
• 指标澄清： 综述批判性地分析了交叉熵基准（XEB）保真度，讨论了经典算法在不模拟完整电路的情况下“伪造”高 XEB 值的漏洞，并区分了弱反驳与强反驳。
• 理论去量子化： 本文详述了 Max-E3LIN2 优化和推荐系统中的理论优势是如何丧失的，因为经典算法（例如 Barak 等人以及 Ewin Tang 提出的算法）在相似的输入假设下达到或超过了量子性能。
• 纠错进展： 表 2 和第 4 节总结了纠错实验的快速进展，指出从简单的重复码到距离高达 7 的表面码的过渡，以及谷歌 2024 年实验的最新里程碑，其中逻辑错误率降至物理错误率阈值以下。

结果

• 实验的不稳定性： 综述发现，几乎所有主要的量子优势实验声明都面临重大挑战。
  • 谷歌 2019 年 RCS（53 个量子比特）： 最初声称经典运行时间为 10,000 年。这一声明受到张量网络优化的挑战，并最终在 2024 年被 Zhao 等人强反驳，他们使用 1,432 个 GPU 在 86.4 秒内模拟了该实验。
  • 中科大 GBS（九章 1.0、2.0、3.0）： 优势声明被 Oh 等人（2023）弱反驳，他们利用张量网络以远快于量子设备的速度模拟了这些实验，尽管对于最大规模的实例，这些实验在“强”意义上仍未被反驳。
  • IBM QSim（2023）： 关于模拟横场伊辛模型的优势声明，在数周内被多种经典方法（张量网络、置信传播、克利福德微扰理论）在笔记本电脑或单个 GPU 上运行所反驳。
  • D-Wave（2024）： 最近关于量子模拟优势的声明在撰写本文时未被反驳，但作者指出它很可能是未来经典挑战的目标。
• 理论转变： 本文表明，理论优势并非静止不变。推荐系统和近似优化（QAOA）的算法，其量子优势已被利用类似数据结构或近似技术的“去量子化”经典算法所侵蚀。
• 纠错里程碑： 虽然容错量子计算尚未实现，但综述强调，逻辑量子比特现在的寿命已超过其物理组件，且错误率正接近实现可扩展容错所需的阈值。

意义与主张

本文主张，量子优势的历史是一个动态的、不断移动的目标，而非静态的成就。

• 移动的目标： 作者强调，计算优势是相对于特定时间点的已知最佳经典算法和硬件来定义的。随着经典算法的改进（通常受量子见解启发），优势的边界会重新移回经典计算机。
• 验证危机： 本文相当一部分内容强调了验证量子优势的困难。许多当前实验（如 RCS）在经典上难以验证，造成了一种悖论：优势声明依赖于那些本身即不可处理的经典计算。本文指出了“峰值电路采样”和“隐藏代码采样”作为未来高效可验证优势的建议方向。
• 纠错的作用： 综述提出，对于具有已证明指数级加速的算法（如肖尔算法），“最后疆域”不仅仅是量子比特数量，而是量子纠错。如果没有容错性，纠错的开销可能会抵消任何理论上的加速。
• 适度的展望： 作者得出结论，虽然针对特定问题很可能存在量子优势，但该领域目前正处于量子与经典主导地位的“边界”上。他们警告不要假设永久性的优势，指出随着经典和量子技术的演进，其状态可能会继续发生变化。本文作为历史记录，旨在推动研究人员转向新的问题表述，这些问题在经典上难以处理、在量子上易于处理、可高效验证且具有科学效用。