⚛️ quantum physics

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

本文为在随机电路采样中实现高线性交叉熵基准分数建立了紧致的量子查询下界，证明了超过理想性能需要 $\Omega(N^{1/3})$ 次查询，并证明了输出具有近乎最优的平滑最小熵，从而为针对纠缠对手的认证随机性提供了严格的安全保证。

原作者： Keshav Bhateja, Mehdi Esmaili, Atul Mantri

发布于 2026-10-06

📖 1 分钟阅读🧠 深度阅读

原作者： Keshav Bhateja, Mehdi Esmaili, Atul Mantri

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

在证明量子计算机能够完成经典机器无法完成的任务这一竞赛中，科学家们转向了一种特定的实验：要求量子设备生成一组随机数。这些数字不仅仅是普通的随机字符串；它们是从一个由随机量子电路创造的复杂且不可见的模式中提取出来的。为了检查设备是否正常工作，研究人员使用了一种称为线性交叉熵基准（linear cross-entropy benchmark）的评分系统。该分数衡量了设备选择出的数字在多大程度上符合理想量子机器最常选择的数字。如果设备是诚实的且运行完美，它会获得一个特定的高分。如果它只是在进行随机猜测，则会得到一个低得多的分数。多年来，这项测试一直是声称实现“量子优越性”的金标准，但一个关键问题一直悬而未决：高分是否真的能证明设备正在生成真正的、不可预测的随机性？一个聪明的对手可能会通过仅仅记住最可能的答案来操纵设备，使其得分很高，从而使输出变得可预测，尽管得分看起来很好。

弗吉尼亚理工大学的一个研究小组现在以数学上的确定性回答了这个问题，为高分究竟能证明什么以及不能证明什么建立了严格的界限。他们证明，对于一个量子设备而言，若要比表现最好的诚实机器得分还要高，它必须执行大量的内部操作，其数量远超任何高效的经典计算机所能处理的范围。具体而言，他们表明，要比理想得分高出一个固定的量，设备需要进行的查询次数与总可能结果的立方根成正比。这一结果充当了一个基本限制，类似于高速公路上的限速，确保没有任何高效的技巧可以伪造出高分。此外，他们还证明，如果一个设备的得分保持在理想得分的一个极小范围内，那么它的输出就是真正不可预测的。即使是一个构建了该设备、并与该设备共享秘密量子链路、且在事后了解了整个设置过程的对手，也无法以任何显著的准确度猜中输出。该设备实际上产生了接近最大可能的随机量，仅伴随着极小的、不可避免的信息损失。

研究人员通过开发一种新的方法来追踪量子算法在查询未知系统时所取得的“进展”而得出这些结论。想象一下，一台量子计算机试图通过用探测器探测来学习一个隐藏物体的形状。该团队创建了一个数学度量，对于一个仅仅是诚实遵循规则的设备，该度量从零开始。他们证明，每当设备进行一次查询以了解更多关于系统的信息时，这个进展度量只能增长极小的量。要达到超过诚实机器的得分，设备需要积累足够的进展来突破一个障碍，但数学表明这需要极其庞大的步骤。这种方法使他们能够缩小理论可能性与被证明的必要性之间的差距，证实了一个关于伪造这些结果之难度的长期猜想。

除了证明伪造结果的限制之外，该论文还描述了一种实际上可以实现这些高分的特定算法，但它只能通过使用允许的最大查询次数来实现。这种“平方算法”（squoring algorithm）的工作原理是获取多个样本，存储它们，然后使用一种称为振幅放大（amplitude amplification）的技术来提升在这些样本中找到匹配项的概率。这个过程有效地将概率分布进行了“平方”，使得最可能的输出比诚实机器更受青睐。这种算法的存在证明了他们发现的下界是紧致的（tight）；它不仅是一个理论上的墙，还是一个需要特定且资源密集型攀登才能到达的巅峰。这种双重性——既证明了你无法轻易伪造结果，又展示了合法获胜究竟有多难——为整个景观提供了完整的图景。

这项工作对认证随机性的意义是深远的。在许多安全应用中，我们需要生成的随机数即使是构建生成器的人也无法预测。这项研究确认，如果一个量子设备通过了标准测试且得分非常接近理想值，那么它生成的比特串所包含的随机性几乎等同于其自身的长度。对于一个拥有 60 个量子比特（可产生 60 位比特字符串）的设备，接近完美的得分保证了其输出包含大约 54 位真正的、经过认证的随机性。即使面对一个与设备纠缠在一起并了解其构造细节的对手，这一结论依然成立。唯一损失的信息是与设备进行的查询次数相关的微小量，这在实际应用中是可以忽略不计的。

这项工作还扩展到了其他类型的量子采样，包括用于光粒子光子实验的采样。研究人员表明，同样的规则也适用：要超越理想得分，设备必须执行特定的大量操作；而要保持在理想得分附近，设备必须产生真正的随机性。他们甚至将这些发现与另一个问题联系起来：创建一个“碰撞分布”（collision distribution），即要求设备输出更容易相同的数字对。他们发现，生成这种特定类型的分布同样需要立方根数量的查询，从而将这些看似不同的任务统一在一个单一的数学法则之下。

该研究并不声称目前的量子计算机已经完美无缺。现实世界的设备由于噪声和误差，得分往往远低于理想水平。然而，论文确立了实现可能性的理论天花板和地板。它告诉我们，如果我们看到一个设备的得分接近顶峰，我们就可以相信它正在进行真正的量子运算并产生真实的随机性。相反，如果一个设备声称正在生成随机性，但无法在不进行不切实际的步骤的情况下达到这一得分，那么我们就知道它并没有在做它所声称的事情。这项研究为从实验演示转向可靠、经过认证的量子随机性提供了严密的理论基础，确保了量子安全的未来建立在坚实、经过验证的土地之上。

技术摘要：量子采样中的紧查询下界及其在认证随机性中的应用

问题陈述
随机电路采样实验是量子计算优势的主要展示方式，通常使用线性交叉熵基准（XEB）进行验证。XEB 分数衡量设备的输出分布与理想分布 $p$ 的一致程度，其计算方法是返回字符串 $z$ 的 $N p(z)$ 的平均值，其中 $N=2^n$ 。虽然高分表明存在量子优势，但它本身并不保证设备确实是从 $p$ 中采样的，也不保证输出是随机的。一个设备可以通过确定性地输出最可能的字符串（而对手可能已知该字符串）来获得高分，从而无法产生认证的随机性。

本文在量子查询模型中探讨了两个基本问题：

分数极限：高效量子设备的得分相对于理想得分能有多高？具体而言，高效设备能否超过理想得分一个常数？
随机性认证：如果一个设备的得分接近理想值，其输出包含多少平滑最小熵（认证随机性），即使面对一个可能与设备纠缠并随后获知算符（电路或函数）的对手（Eve）？

方法论
作者在查询模型中开展工作，其中电路被替换为一个从已知系综中抽取的算符。他们分析了两种特定的系综：

傅里叶采样（Fourier Sampling）：算符是一个均匀随机函数 $f: \{0,1\}^n \to \{\pm 1\}$ 。诚实采样器的得分约为 3。
Haar 随机态（Haar-Random States）：算符隐藏了一个均匀随机单位向量 $|\phi\rangle$ （通过规范态制备算符或 Haar 随机酉矩阵访问）。诚实采样器的得分约为 2。

核心方法论涉及定义一个进度度量（progress measure） $\lambda$ ，用于量化设备的态与“诚实”态（进行单次查询的态）之间的偏差。分析遵循三步框架：

得分界限：期望得分 $B(A)$ 由进度度量进行限制： $B(A) \leq \text{理想得分} + O(\lambda + \lambda^2)$ 。
增长界限：研究表明，每次查询仅使 $\lambda$ 增加 $O(\sqrt{(t+1)/N})$ ，其中 $t$ 是之前查询的次数。因此，经过 $q$ 次查询后， $\lambda = O(q^{3/2}/\sqrt{N})$ 。
随机性提取：对于得分接近理想值的设备（缺陷 $\delta$ 很小），通过改进得分证明过程，证明设备的输出分支接近特定的辅助向量。这些向量由仅作用于设备的算符生成，其范数受 $\text{poly}(q)\sqrt{p(z)}$ 限制。这种结构意味着，即使 Eve 知道算符，她猜测输出的能力也是有限的。

主要贡献与结果

1. 关于超过理想得分的紧下界
本文确立了理想得分对于高效量子设备而言是一个“Tsirelson 界”。

查询复杂度：要使得分超过理想得分一个常数 $\epsilon$ $ϵ$ ，量子算法需要 $\Omega(N^{1/3})$ $Ω (N^{1/3})$ 次查询。
- 对于傅里埃采样，期望得分为 $3 + \epsilon$ 需要 $q \geq \Omega(N^{1/3})$ 。
- 对于Haar 随机态，期望得分为 $2 + \epsilon$ 需要 $q \geq \Omega(N^{1/3})$ 。
上界：作者证实，使用“平方算法”（一种碰撞查找算法的变体）只需 $O(N^{1/3})$ 次查询即可使得分超过理想得分一个常数。该算法存储 $m \approx N^{1/3}$ 个理想样本，并利用振幅放大将输出向理想分布的平方 $p(z)^2$ 偏置。
紧致性：这些界限是紧致的；诚实采样器（1 次查询）与能够显著超过理想得分的能力之间的差距，被精确地刻画为 $N^{1/3}$ 阈值。

2. 理想得分下的认证随机性
本文证明，进行多项式次查询且得分在 $o(1)$ 范围内接近理想值的设备，其输出具有近乎最大的随机性。

最小熵：对于傅里埃采样和 Haar 随机态（通过规范算符），输出 $Z$ 的平滑最小熵满足 $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$ ，其中 $R$ 是算符， $E$ 是 Eve 的寄存器。
对抗模型：即使 Eve 与设备纠缠，并在设备输出 $Z$ 后获知算符（函数 $f$ 或向量 $\phi$ ) 的完整描述，该结论依然成立。
参数：平滑参数 $\eta$ 随 $\text{O}(\sqrt{\delta} + q^{3/4}N^{-1/4})$ 缩放。如果缺陷 $\delta$ 忽略不计且 $q$ 是 $n$ 的多项式，则平滑量是微不足道的，从而认证了 $n - O(\log n)$ 比特的随机性。
最优性： $O(\log n)$ 的损失被证明是近乎最优的。作者构造了使用振幅放大技术的设备，这些设备实现了接近理想的得分，但将输出限制在一个大小为 $N/q^2$ 的已知集合内，从而将最小熵限制在 $n - 2\log q$ 。

3. 其他结果

碰撞分布：本文展示了采样碰撞分布（正比于 $p(z)^2$ ）的查询复杂度为 $\Theta(N^{1/3})$ 。
量子 Hadamard 积：文中提出了一个相干版本的平方算法，用于制备具有均匀振幅幅值的两个态的量子 Hadamard 积。该算法使用 $O(N^{1/3})$ 次查询实现 $O(N^{-1/6})$ 的迹距离误差，优于标准振幅放大所需的 $\sqrt{N}$ 次查询。

意义与主张
本文声称为量子采样任务提供了无条件的、信息论层面的保证，解决了关于“量子优越性 Tsirelson 不等式”的开放问题。

类比 CHSH：结果与 CHSH 博弈有着直接的平行关系。正如 Tsirelson 界（ $\cos^2(\pi/8)$ ）限制了量子策略的获胜概率并在该界处认证随机性一样，理想的 XEB 分数限制了高效量子采样器的性能，并在接近该得分时认证了随机性。
无条件安全性：不同于以往依赖计算硬度假设或限制对手知识（例如未获知完整算符）的结果，这项工作提供了针对获知算符并持有任意纠缠的对手的无条件界限。
局限性：作者指出，其结果适用于算符模型。对于现实世界的设备（如 [AAB+19] 中的设备），目前的得分远低于理想值（例如 1.002 对比 2），这意味着目前实验设置中对于认证随机性的保证依赖于不同的、较弱的假设（如 [AH23]）。此外，对于 Haar 随机态，该结果需要规范态制备算符而非完整的酉矩阵访问，因为学习完整 Haar 随机酉矩阵的对手可能会将输出与该酉矩阵的列相关联。

综上所述，本文严格定义了高效量子采样的极限，证明了理想得分是高效设备的硬性障碍，并且接近该障碍可以认证近乎所有的随机性，即使面对强大的量子对手。

类似论文