🔢 mathematics

Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

本文通过提出一种能在线性时间内生成统计上不可区分样本的高效经典“冻树”（frozen-tree）算法，对随机电路采样中量子优越性的前提提出了挑战，并认为真正的计算难度在于识别特定的电路实现，而非从底层的狄利克雷分布中进行采样。

原作者： Sangchul Oh

发布于 2026-07-07

📖 1 分钟阅读🧠 深度阅读

原作者： Sangchul Oh

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大背景：“量子魔法”挑战

想象一场高风险的“猜图案”游戏。科学家们声称，量子计算机可以完成经典计算机无法完成的任务：生成一种特定类型的随机 0 和 1 字符串（就像数字化的硬币投掷序列），这种序列极其复杂，以至于经典计算机永远无法预测或复制它。这项任务被称为随机电路采样 (Random Circuit Sampling, RCS)，并一直被用作证明量子计算机优于经典计算机的核心证据。

本文作者 Sangchul Oh 表示：“等一下。你不需要量子计算机也能做到这一点。我用一台普通的笔记本电脑就能完成，而且我做得更快。”

核心思想：“冻结树” (The Frozen Tree)

为了理解作者是如何实现这一点的，让我们用一个巨大的神奇树来做类比。

量子的主张： 当量子计算机运行随机电路时，它会创造出一片“森林”的可能性。每当你向它索要一个答案时，它都会在森林中选择一条路径。其主张是，这片森林是如此混乱和纠缠，以至于经典计算机（比如你的笔记本电脑）无法弄清楚森林的规则，从而无法选择相同的路径。
作者的发现： 作者发现这个“混乱的森林”实际上拥有一个隐藏的、完美的结构。它看起来像一棵二叉树（每个分支都分裂成两个的分支）。
- 在顶端（根部），树木发生分裂。
- 在下一层，这些分支再次分裂。
- 这个过程一直持续到最底层的叶子，而叶子代表了最终的 0 和 1。

其中的秘诀是一个叫做“条件尺度不变性”（Conditional Scale Invariance）的规则。用通俗的话说，这意味着这棵树是自相似的。树顶分裂的方式在统计学上看起来与树中间一半处的分裂方式，以及在接近叶子前的分裂方式是完全一致的。这就像分形（fractal）一样：整体的模式在每一个微小的局部都在重复。

“冻结”的小技巧

这是聪明之处所在。作者意识到，要模拟这个量子树，你不需要一次性计算整个结构。你只需要在穿行过程中逐步构建它。

行走： 想象你正在从树顶向叶子行走。在每一个岔路口，你必须决定：“我是向左走（0）还是向右走（1）？”
“冻结”时刻： 在真实的量子实验中，这些决策是由量子机器做出的。在作者的经典方法中，当你第一次到达一个岔路口时，你会抛掷一枚特殊的硬币，来决定分裂比例（即向左或向右走的概率）。
- 至关重要的一点是： 一旦你抛出了这枚硬币并确定了该特定岔路口的比例，你就将其**“冻结”**。你把它记录下来。
- 如果你（或其他人）再次访问同一个岔路口，你将使用完全相同的那个冻结比例。你不会再次抛掷硬币。

因为这棵树是以这种方式被“冻结”的，作者可以极其快速地生成这些随机字符串。论文声称这只需要 O(n) 时间，这意味着如果比特数增加一倍，工作量也仅增加一倍。它是线性的且高效的。

“统计孪生”论证

该论文对结果提出了一个非常强力的主张：

量子结果： 量子计算机根据特定的随机电路产生一组数字。
经典结果： “冻结树”算法根据树的结构产生一组数字。

作者通过数学证明，这两组列表都来自完全相同的统计族（称为狄利克雷分布/Dirichlet distribution）。

这就像是两个不同的面包师在制作巧克力碎曲奇饼干。

面包师 A（量子）使用了一个秘密且混乱的烤箱。
面包师 B（经典）使用了一个精确的冻结模具。

论文指出，如果你交给一位蒙着眼睛的评委一个来自面包师 A 的曲奇和一个来自面包师 B 的曲奇，他们无法分辨两者的区别。 这些曲奇（数据）在统计学上是完全相同的。

为什么这很重要（根据论文观点）

目前，科学家们说：“看！量子计算机产生了这些奇怪、复杂的图案，而经典计算机无法制造这些图案。因此，量子计算机正在获胜。”

作者说：“那不是真的。我们刚刚展示了，利用‘冻结树’方法，经典计算机可以瞬间产生那些完全相同的图案。”

如果经典计算机可以完美模仿量子输出，那么针对这项特定测试的“量子优势”（即量子计算机正在做经典计算机做不到的事情这一观点）就消失了。

“噪声”因素

真实的量子计算机是杂乱无章的；它们会产生错误（噪声）。论文还展示了“冻结树”方法可以轻松模拟这些错误。无论量子计算机产生的是“去极化噪声”（随机静电）、“振幅阻尼”（能量损失）还是“读取错误”（读错结果），经典的“冻结树”都能完美地模拟这些误差。

论文得出结论：没有任何仅基于最终数字列表（样本）的测试可以证明量子计算机正在做一些特别的事情。其“难度”并不在于随机性本身，而是在于弄清楚量子计算机到底构建了哪一棵特定的树。但既然统计结果是相同的，那么这项基准测试就失效了。

一句话总结

该论文声称，随机量子电路的“魔力”实际上只是一个隐藏的、自相似的树状结构，经典计算机可以通过在向下行走的过程中“冻结”其决策，从而完美且瞬间地复制这种结构，这意味着目前的量子优势测试存在缺陷。

技术摘要：冻结树采样算法驳斥了随机电路采样的量子优势

问题陈述
随机电路采样（Random Circuit Sampling, RCS）目前被视为展示量子优越性的主要基准，其目标是采样由随机电路生成的哈尔随机（Haar-random）量子态所产生的比特串。普遍的假设认为这一任务在经典计算上是难以处理的，因为随机量子态具有高度纠缠且缺乏可利用的模式，表现出诸如指数输出分布、线性交叉熵基准（XEB）得分、重输出生成（heavy output generation）以及反集中性（anti-concentration）等统计特性。本文对这一前提提出了质疑，认为这些统计特性并不构成量子优越性的证据，并指出 RCS 的难度往往被误认为是采样底层概率分布的难度，而非识别特定电路实现的难度。

方法论：冻结树采样器（The Frozen-Tree Sampler）
作者提出了一种名为冻结树采样器的经典算法，该算法利用了哈尔随机量子态的精确条件尺度不变性（exact conditional scale invariance）。其核心理论洞察在于，寻找一个比特串 $x$ 的概率 $p(x) = |\langle x|\psi\rangle|^2$ 可以表示为一次二叉树遍历。

树表示法： 联合概率通过链式法则分解为条件概率的乘积：
$p(x) = \prod_{k=1}^n R_{x_{<k}}^{1-x_k} (1 - R_{x_{<k}})^{x_k}$
其中 $x_{<k}$ 是前 $k-1$ 个比特的前缀。“分支比例”（branch ratios） $R_u$ 在每个节点 $u$ 处是独立的随机变量，服从 Beta 分布：
$R_u \sim \text{Beta}(K, K), \quad \text{其中 } K = 2^{n-|u|-1}.$
这种结构源于 Dirichlet 分布的聚合属性以及随机态的条件尺度不变性。
采样算法： 采样器执行从根节点到叶节点的随机游走（ $n$ 步）。
- 惰性生成（Lazy Generation）： 算法并非预先计算所有 $2^n - 1$ 个分支比例，而是按需生成。当访问到一个新节点 $u$ 时，会从 $\text{Beta}(K, K)$ 中抽取一个比例 $R_u$ ，并将其“冻结”（存储或通过以节点身份为键的伪随机函数进行确定性再生）。
- 效率： 该算法在 $O(n)$ 时间内生成一个比特串。对于 $M$ 个样本，总运行时间为 $O(Mn)$。
- 噪声建模： 该框架通过对树结构或最终比特串应用仿射变换或混淆矩阵，自然地纳入了噪声通道（全局去极化、振幅阻尼、读取误差），同时保持 $O(n)$ 的复杂度。

关键结果

统计同一性： 作者证明了冻结树采样器的输出概率 $p_F(x)$ 与随机量子电路的输出概率 $p_C(x)$ 是同一个 $(N-1)$ 单形上平坦 Dirichlet 分布的独立实现。因此， $p_F(x) \stackrel{d}{=} p_C(x)$ 。
不可区分性： 由于两者在统计上是相同的，任何仅作用于采样比特串的统计检验（如 XEB、重输出生成或反集中性检验）都无法将经典的冻结树采样器与量子随机电路区分开来。
性能： 对于 $n=1000$ 个量子比特，该采样器在几秒钟内即可生成 $10^7$ 个样本。相比之下，谷歌的 Sycamore 处理器在 $n=53$ 时收集 $\sim 10^6$ 个样本需要约 200 秒。
噪声重现： 冻结树采样器能够精确重现由噪声（例如振幅阻尼导致的指数峰值和尾部行为受抑）引起的统计失真，而无需从有限样本中进行经验估计。

意义与主张
本文声称，如果将任务定义为对随机态的 Dirichlet 分布进行采样，则 RCS 的量子优势无法经受住审查。

RCS 的“难度”不在于采样过程本身（该过程在经典计算上是高效的， $O(n)$ 每个样本），而在于从电路到其振幅的具体映射过程。
由于冻结树采样器可以高效地（经典地）重现所有标准验证指标（指数分布、XEB 等），因此这些指标不能作为量子优越性的独立证据。
作者总结道，RCS 作为目前的验证方式，并不是一个可靠的独立量子优越性基准。他们指出，任何残余的优势必然存在于电路特定的实现中，这一点在其关于“Hurwitz–frozen-tree 电路”（该电路允许高效经典采样）的配套工作中进行了讨论。