⚛️ quantum physics

Verifiable quantum advantage in extremely low depth

本文提出了一种可通过极浅层量子电路（无论是 $\mathsf{QNC}^0[\log\log]$ 还是 $\mathsf{QAC}^0$ ）解决的采样问题，该问题在基于格的假设下在经典计算上是困难的，且能被经典计算机高效验证，从而在无需中途测量或前馈的情况下展示了可验证的量子优势。

原作者： Alexandru Gheorghiu

发布于 2026-09-02

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Alexandru Gheorghiu

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

在探索量子计算机真实力量的过程中，科学家们不断提出一个看似简单实则深奥的问题：要解决一个经典计算机无法解决的问题，究竟需要多少量子机制？几十年来，主流观点认为，要获得决定性的优势，量子系统需要进行复杂且深度的计算，将数千个操作编织成一个漫长而复杂的序列。这种深度被认为是机器能够探索那些对普通计算机而言依然隐藏着的可能性的独特能力的来源。然而，一种新的研究方向正在挑战这一直觉，它在探究最受限、最浅层的量子电路——即那些仅执行少量操作的电路——是否仍能战胜最优秀的经典算法。由于这项研究意义重大，如果这样一个极简的量子系统能够解决一个难题，就证明了量子优势不仅仅是大型、易错机器的特征，而是即使是最简单的量子结构也具备的一种基本属性。至关重要的是，为了使这种优势具有实用价值，使用标准计算机的人类观察者必须能够快速且确定地验证结果，从而将理论上的可能性转化为实际的测试。

一位研究人员现在构建了一个特定的数学谜题，展示了这一现象。他们设计了一个任务，量子计算机可以使用一个极其浅层的电路来解决该任务，这个电路如此短促，以至于几乎只达到了基础逻辑门的高度。然而，假设某些标准的数学难度依然成立，任何在合理时间内运行的经典计算机都无法有效解决同一个谜题。使这一成就尤为引人注目的在于，其解法并非一个“黑箱”；经典观察者可以高效地检查答案，并确认量子机器确实完成了这一壮举。该研究人员通过两种不同的方式构建了量子求解器。第一种使用稍深一点的电路，但仅依赖于量子比特之间标准的、简单的连接。第二种则更为令人赞叹，它使用了一个常数深度的电路，这意味着无论问题规模如何扩大，其深度都不会增加，但它需要一种可以同时处理多个输入的特定类型的门。这两个版本都在经典计算机失败的地方取得了成功，并且都能产生可被瞬间验证的结果。此外，由于具有无界扇入（unbounded fan-in）能力的电路可以由具有无界扇出（unbounded fan-out）能力的电路模拟，因此该任务也可以由后者解决，尽管作者强调了常数深度无界扇入的版本是更显著的成就。

这项发现的核心在于研究人员如何将一个已知的密码学挑战转化为适合这些浅层机器的形式。他们从一个基于在噪声数据中寻找隐藏模式（这一概念被称为“容错学习”，learning with errors）的难题出发。在以往尝试利用类似思路证明量子优势的研究中，量子计算机必须执行一个涉及在计算过程中进行测量并将结果反馈回机器以引导下一步操作的长时多步过程。这种“交互式”方法要求量子态在很长时间内保持相干和稳定，而这在实际维护中是非常困难的。这项新工作完全绕过了这一点。研究人员开发了一种方法来编码该问题，使得量子计算机可以运行一段单一、短暂且不间断的操作序列，然后在最后仅进行一次测量。这消除了对中途测量和反馈的需求，显著简化了硬件要求。

为了实现这一点，研究人员不得不依赖比早期研究中更强的一套数学假设。他们引入了一个关于在模系统下进行加法运算时，某些信息位（即进位位）行为的特定条件。虽然这一假设尚未在标准数学中得到证明，但作者提供了支持其有效性的有力证据。他们认为，如果一台经典计算机能够解决他们的谜题，就意味着打破了这些底层的数学假设，而这在广泛认知中是不可能的。这一结果有力地证明了浅层量子电路拥有足够的内部结构来解决经典难题。研究人员展示了量子机器如何准备许多可能输入的叠加态，通过局部且浅层的编码进行处理，然后测量输出以揭示编码解决方案的模式。

这项工作的意义是双重的。首先，它缩小了理论可能与实际可实现之间的差距。通过展示常数深度电路可以实现这种优势，这项研究表明，未来的量子“量子性”测试可能并不需要目前工程技术尚无法实现的庞大且深层的电路。其次，它明确了量子力量与经典力量之间的边界。研究人员明确指出，他们的结果同样适用于具有无界扇出门的电路，这是一种已知比其常数深度无界扇入模型计算能力更强的不同类型的强大操作。相反，他们的成功依赖于其编码的特定结构以及底层格问题（lattice problems）的难度。该研究并不声称解决了构建通用量子计算机的问题，也不暗示这些浅层电路可以分解大数或破解当前的加密算法。相反，它提供了一个精确且可验证的采样任务，作为一个清晰的基准。

该构造涉及一个“挑战与响应”协议，验证者向证明者发送一个公钥。证明者（充当量子机器）准备一个量子态，应用浅层电路，并返回一组数字。验证者随后检查这些数字是否满足特定的关系。如果证明者是经典计算机，即使采用最佳策略，它也无法在超过四分之三的情况下产生正确关系。如果证明者是诚实的量子机器，它几乎每次都能成功。研究人员证实，他们的量子实现仅使用多项式宽度的量子比特，这意味着量子比特的数量随问题规模合理增长，而深度保持极低。这种低深度、经典硬度和高效验证的平衡，标志着理解量子优势最小需求的重要一步。

虽然这项研究依赖于尚未完全证明的假设，但作者谨慎地将其结果设定为以这些数学信念为前提。他们承认，所使用的特定“进位谓词”（carry-predicate）假设是该领域的一个新加入项，尽管他们提供了支持其可能成立的部分证据。这种透明度确保了科学界可以进一步测试和完善这些假设。这项工作也强调了当前方法的局限性；例如，他们指出，若要进一步降低电路深度以仅使用标准门（而不使用特殊的扇入门），仍然是一个开放性的挑战。研究人员建议，要实现一个仅使用简单门的真正常数深度电路，可能需要目前难以找到的新型数学构造。

最终，这篇论文提供了一个具体的例子，展示了量子系统如何在资源极小化的条件下超越经典系统。它将对话从抽象的复杂度理论转向了一个切实的、可验证的协议。通过剥离对深层电路和中途测量的需求，研究人员展示了量子优势的本质可以在非常浅层的结构中被发现。这一发现拓宽了早期量子设备可能实现的视野，并为测试一台机器是否真正利用了量子力学提供了一个新的、严谨的标准。未来的路径包括完善这些假设，并探索是否可以将类似的技巧应用于其他密码学任务，但核心结果依然成立：一个浅层量子电路确实可以解决一个对经典计算机而言很难、但对验证而言很容易的问题。

技术摘要：极低深度下的可验证量子优势

问题陈述
本文旨在解决量子复杂度理论中的一个基本空白：缺乏一种任务，能够同时满足由极浅量子电路求解、对多项式时间经典算法而言具有难度，且能被经典计算机高效验证。以往的研究已经证明，常数深度量子电路（特别是具有无界扇出能力的 $QNC^0_f$ ）可以解决经典难题，并且存在量子性的交互式证明，但目前尚无已知的“白盒”问题能在仅使用有界入度门（bounded-arity gates）的亚对数深度或具有无界入度（unbounded fan-in）的常数深度下，同时满足这三个标准。具体而言，现有的低深度量子性证明通常依赖于中途测量（mid-circuit measurements）、经典前馈（classical feed-forward）或黑盒随机预言机（black-box random oracles），这些方式模糊了电路深度的保证，或者需要无界扇出门。核心问题在于，是否可以在受限的类别 $QNC^0[\log \log]$ （具有有界入度的对数对数深度）和 $QAC^0$ （具有无界入度的常数深度）内实现可验证的量子优势。

方法论
作者构建了一个基于学习误差（Learning with Errors, LWE）框架的采样问题，通过将 Arabadjieva 等人 [AGGM25] 的单轮量子性证明编译为极低深度的电路。其核心技术创新是利用随机编码（randomized encodings），将基于 LWE 的陷门无环函数（trapdoor claw-free functions, TCFs）的评估转化为局部、浅层的计算。

协议结构： 该协议是一个单轮挑战-响应任务。验证者采样一个基于 LWE 的 TCF $f$ ，或一个基于格知识假设（lattice knowledge assumption）的单射函数 $g$ ，两者在计算上是不可区分的。证明者必须返回一个响应 $(y, d)$ （或其编码等价物），该响应需满足特定的代数关系。
随机编码： 为了实现低深度，作者将二进制仿射映射编码推广到了环 $\mathbb{Z}_q$ $Z_{q}$ 上的映射。该编码将 $Mv + \eta$ $M v + η$ （其中 $M$ $M$ 是矩阵， $v$ $v$ 是输入向量， $\eta$ $η$ 是噪声）的全局计算替换为一系列局部可计算的符号。
- 路径掩码编码（Path-Mask Encoding）： 输入之和通过“路径掩码”（ $h$ ）进行编码，这些掩码在路径上输送随机值，并在求和时相互抵消。这确保了每个输出符号仅依赖于常数个源值。
- 输入掩码（Input Masking）： 为了防止跨行输入复用（这会破坏局部性），应用了第二层掩码（ $r$ ）。
- 局部性： 每个编码符号最多依赖于三个源单词（输入、掩码或噪声）。这使得量子证明者可以并行执行编码评估。
量子策略： 诚实的量子证明者在分支位、输入、噪声和编码掩码的叠加态上进行准备。它执行局部编码，擦除噪声寄存器（此时噪声已与输出纠缠），并在 Hadamard 基下进行测量。这产生了一个方向 $D$ 和一个比特 $C$ ，它们满足由 TCF 的“爪”（claw）结构导出的奇偶关系。
验证： 验证者使用陷门来检查图像的有效性（在单射情况下），或恢复两个原像及其相关的掩码（在 TCF 情况下），以验证奇偶方程。

关键假设
该问题的经典硬度依赖于两个非标准但动机充分的假设：

次指数级格点知识（Subexponential Knowledge-of-Lattice-Point, LK-1/4）： 一个输出接近格点点的算法必须“知道”最近的格向量。这被用于提取单射函数 $g$ 的原像。
带有进位谓词的自适应硬核比特（Adaptive-Hardcore-Bit with Carry Predicates）： 这是 LWE 的一种强化的自适应硬核比特属性。它假设没有任何高效的经典算法可以预测包含线性项以及由 LWE 方程部分和产生的“进位比特”的秘密的奇偶性。作者为该假设提供了证据，但指出目前尚不清楚它是否直接遵循标准的 LWE。

结果
论文展示了两种量子采样器的实现：

$QNC^0[\log \log]$ ： 使用仅有一位和两位门（有界入度）的深度为 $O(\log \log \lambda)$ 的电路。
$QAC^0$ ： 使用无界入度门（广义 Toffoli 门）的常数深度 $O(1)$ 电路。

定理 1.1（非正式）： 在所述假设下，存在一类采样问题，其中：

诚实的量子采样器以概率 $1 - \text{negl}(\lambda)$ 被接受。
任何运行时间为 $2^{o(\lambda)}$ 的均匀经典采样器被接受的概率至多为 $3/4 + \text{negl}(\lambda)$ 。
量子计算不需要中途测量或前馈；它由单个幺正电路及随后的最终测量层组成。

意义与主张
本文声称提供了第一个不需要无界扇出门（无界扇出门足以使深度层级坍缩）或中途测量的可验证量子优势。通过使用随机编码编译 AGGM 协议，作者证明了即使在没有无界扇出或交互式反馈的情况下，浅层量子电路也具备解决其解可被高效验证的经典难题所需的结构。

作者对局限性保持了谦逊的态度：

该构造依赖于非标准的“进位谓词”假设，目前尚未证明该假设直接遵循标准 LWE。
电路宽度是多项式级的但规模巨大（估计为 $e^{O(\lambda^4 \log^6 \lambda)}$ ），这使得近期的实验实现并不可行。
该结果尚未实现仅使用有界元数门（bounded-arity gates）的真·常数深度电路（真正的 $QNC^0$ ），因为对 $L$ 位数（ $L = \Theta(\log^2 \lambda)$ ）的算术运算需要要么 $O(\log \log \lambda)$ 的深度，要么无界入度。

这项工作拓宽了对浅层量子计算的理解，表明即使在没有无界扇出能力或交互式反馈的情况下，量子电路在合理的密码学假设下，仍能保持相对于经典计算的可验证优势。

类似论文