⚛️ quantum physics

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

本文为经典可验证的量子优势以及利用量子不可区分混淆（qiO）进行 BQP 计算的验证构建了协议，为启发式提议提供了严密的密码学基础，并实现了在标准计算假设下的首次公开可验证 BQP 验证。

原作者： Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu

发布于 2026-10-01

📖 1 分钟阅读🧠 深度阅读

原作者： Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu

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

在构建能够解决超越当今计算机处理能力的难题之机的竞赛中，科学家们面临着一个奇特的悖论。为了证明一台新的量子计算机正在正常工作，你必须要求它执行一项如此复杂的任务，以至于标准计算机无法检查其答案。然而，如果答案无法被检查，你又如何知道这台机器不是在瞎猜呢？这就是量子优势的核心张力：需要一种既让经典机器难以伪造，又让人类审计员易于验证的测试方法。多年来，研究人员一直试图设计这些测试，通常依赖于复杂的数学谜题或尚未具备的特定硬件能力。其目标始终是寻找一种方法，在不需要超级计算机在旁监督的情况下，确认一台设备是否真的在利用奇特的量子力学定律。

一组研究人员现在提出了一种解决这一难题的新方法，将问题从硬件工程领域转向了密码学领域。他们发表于2026年10月的工作表明，如果我们能以一种特定的、数学上严谨的方式隐藏计算机程序的内部运作机制，我们就能创造出一种既能在近期的量子设备上轻松运行，又易于任何人验证的测试。其核心思想依赖于一个被称为“混淆”（obfuscation）的概念，这就像是将食谱彻底打乱，使得你仍然可以烹饪出这道菜，但没有人能通过阅读成分表来弄清楚它是如何制作出来的。通过将这种打乱技术应用于量子电路，作者展示了如何创建一个对于经典尝试欺骗具有安全性的“量子性证明”（proof of quantumness）。

研究人员基于这一想法构建了两个主要的协议。第一个是证明设备具有量子特性的测试。在这种情景下，验证者向证明者发送一个挑战。该挑战由若干个经过混淆的指令组成。对于观察这些混얼指令的经典计算机来说，它无法得知这些指令实际在做什么。然而，量子计算机可以运行这些指令并产生特定的结果模式。验证者检查结果是否符合预期的模式。如果符合，验证者便知道证明者一定是量子的。至关重要的是，作者表明通过添加一种特定的密码学成分——后量子安全的单向函数，可以使这项测试具有“公开可验证性”。这使得任何人都可以进行检查，而无需密钥或私密信息，相比之下，初始的私有版本协议则需要验证者保留一个秘密状态。

第二个协议更进一步，允许经典计算机验证特定复杂量子计算的结果，即BQP判定问题。这被称为量子计算的经典验证。研究人员证明，如果这种混淆技术奏效，经典审计员可以将大规模计算委托给量子机器，并确信其结果。他们通过在挑战中隐藏“陷阱”电路来实现这一点。这些陷阱旨在如果机器诚实则揭示答案，但它们被隐藏得极好，以至于试图欺骗的机器无法分辨哪些部分是陷阱，哪些是真实的计算。作者证明，在关于某些数学问题难度的合理假设下，经典机器无法欺骗该系统。

这项工作的重大贡献在于它不依赖于被测试量子计算机的具体硬件。相反，它依赖于打破混淆的数学难度。作者还解决了实际中的一个障碍：真实的量子计算机经常使用额外的“辅助”比特（称为ancillas），这些比特在使用后必须重置为零。他们表明，即使对于这些混乱的、现实世界的电路，他们的混淆方法依然有效，因为可以将它们转换为能够被混淆处理的更简洁的数学形式。这弥合了理论密码学与我们现有的嘈杂、不完美设备之间的鸿沟。

论文还探讨了构建此类混淆是否具有可行性的问题。虽然作者并未提供一个完成的、可运行的混淆器，但他们提供了一份路线图。他们提出了一种构建这些混淆器的方法，即通过将复杂的电路分解为较小的随机碎片，并以一种既保留功能又隐藏结构的方式重新组装。他们证明，如果这种方法对随机电路有效，那么它对任何电路都有效。这种“最差到平均”（worst-to-average）的归约提供了强大的理论基础，表明整个系统的安全性取决于区分随机量子电路的难度，而这被广泛认为是一个难题。

这项工作的意义是深远的。它为最近由其他研究人员提出的“峰值电路采样”（peaked circuit sampling）启发式方法提供了一个严密的密码学基础。通过用可证明的安全性取代启发式的猜测，作者提供了一种从“我们认为这很难”转向“我们可以证明这很难”的方法。他们的工作表明，验证量子计算机的路径并不一定需要更强大的量子硬件或复杂的交互式游戏。相反，它可能在于巧妙地应用密码学隐藏技术，从而允许经典观察者以数学上的确定性来信任量子机器的话语。

研究人员谨慎地指出，他们的结果取决于这些混淆工具的存在。虽然他们还没有制造出这些工具，但他们已经明确了这些工具需要具备哪些属性以及如果它们存在该如何使用。他们还表明，其系统的安全性并不需要除了混淆的存在以及（对于公开验证而言）单向函数之外的任何额外的、未经证实的关于未来计算能力的假设。如果混淆成立，则验证成立。这种关注点的分离允许科学界专注于构建混淆工具，同时拥有一个清晰的、经过验证的框架来指导其用途。

最后，这篇论文并不声称已经解决了量子验证问题并交付了一个成品。相反，它绘制了一幅精确的地形图。它表明，如果我们能有效地打乱量子程序，我们就能完美地验证它们。它用密码学证明的确定性取代了启发式测试的不确定性。对于量子计算领域而言，这是一次从“希望机器正在工作”到“通过数学严谨性获知其正在工作”的转变。这项工作成为了抽象的密码学理论世界与对下一代计算机结果产生信任的实际需求之间的桥梁。

技术摘要：通过量子电路混淆实现可验证的量子优势与计算

问题陈述

本文探讨了在近期时代建立可验证量子优势以及 BQP 计算的经典验证这一根本性挑战。现有的方法面临着一种二分困境：

基于密码学的量子性证明（例如基于陷阱门无分叉函数）：虽然允许高效的经典验证，但需要容错量子硬件，这使得它们在当前的噪声设备上难以实现。
随机电路采样（例如 Google 的 Sycamore 实验）：可以在近期的硬件上实现，但缺乏高效的经典验证；验证输出分布需要指数级的经典资源。

Aaronson 和 Zhang 提出的一个启发式方案（峰值电路采样）试图弥补这一差距，即在复杂电路中嵌入一个隐藏的“峰值”（一个高概率输出字符串），从而在已知峰值的情况下实现高效验证。然而，以往对这些电路进行启发式混淆的尝试已被经典攻击破解。本文探讨了是否可以将此类方案的安全性建立在严谨的密码学假设之上，而非仅仅依赖于启发式的不可区分性。

方法论

作者采用了模块化的密码学方法，将安全性的负担从启发式的电路变换转移到了**量子不可区分混淆（qiO）**这一原语上。

1. 密码学框架

核心方法论依赖于 qiO，其定义为一个经典的多项式时间算法，输入一个量子电路描述，输出一个混淆后的电路描述。其安全保证在于：具有相同“形状”（门数量、量子比特数量）且诱导通道在钻石距离（diamond distance）下近乎相等的两个电路，其混淆后的结果在计算上是不可区分的。

本文构建的协议基于以下假设：

qiO：特别针对无辅助量子比特（ancilla-free）的幺正电路以及整洁电路（tidy circuits，即将辅助量子比特恢复为零的电路）。
复杂度分离：一个稍强的变体，即 $BQP \neq BPP$ ，具体为 $BQP \not\subseteq i.o.BPP$ （BQP 不包含在“无限经常”的 BPP 中）。
后量子单向函数（Post-Quantum OWFs）：用于公开验证协议。

2. 协议构建

作者设计了两类主要的协议：

量子性证明 (PoQ)：
- 私密验证：验证者生成一个随机字符串 $b$ 并混淆一组电路。每个电路要么是恒等映射，要么是位翻转，由 $b$ 决定。证明者在 $|0\rangle$ 上运行这些电路并返回测量后的比特。验证者检查输出是否与 $b$ 相匹配。安全性依赖于混淆后的恒等电路与位翻转电路的不可区分性，这通过归约与 BQP 问题的难度相关联。
- 公开验证：为了消除对验证者秘密状态的需求，验证者发布 $y = f(b)$ ，其中 $f$ 是一个单向函数。证明者返回 $b'$ ，任何人都可以通过验证 $f(b') = y$ 来进行验证。本文证明，存在此类经典安全的 OWF 是由用于 PoQ 的 qiO 和复杂度假设所蕴含的，不需要额外的硬度假设。
BQP 的经典验证 (CVQC)：
- 私密验证：验证者创建一个混淆电路网格。大多数是“测试”电路（简单的位翻转），而少数“植入”的位置包含被随机比特掩盖的目标 BQP 电路 $C$ 。证明者返回一个网格的测量结果。验证者检查测试位置，并对植入位置进行去掩码处理以验证一致性。安全性依赖于由于 qiO 的存在，证明者无法区分植入位置与测试位置。
- 公开验证：类似于 PoQ，验证者发布奇偶校验信息和预期答案的单向图像。这使得任何经典方可以在假设存在后量子 OWF 的情况下，无需秘密状态即可验证结果。

3. 构建 qiO（理论基础）

意识到通用 qiO 是一个很强的原语，本文提出了一条受 Canetti 等人针对经典电路提出的 局部混合框架 (local-mixing framework, CCMR) 启发的构建路径。

归约为无辅助量子比特电路：作者证明，若能构建“整洁”电路（使用辅助量子比特但将其恢复为零）的 qiO，则可以从无辅助量子比特幺正电路的 qiO 中构建出来。这涉及一种编译技术，将整洁电路嵌入到一个更大的无辅助量子比特幺正电路中，从而有效地隐藏了对非干净输入的动作。
最坏情况到平均情况的归约：他们提出了一个归约，表明如果能够混淆随机无辅助量子比特电路，那么就可以混淆任意无辅助量子比特电路。这依赖于两个新的假设：
1. 量子随机输入混淆 (RIO)：能够混淆随机电路，使得输出看起来像经过后处理的理想等价电路。
2. 量子分裂电路伪随机性 (SCP)：能够隐藏一个电路是通过使用随机分隔符进行拆分和重新组合而构建的事实。
3. 稳定性 (Stability)：一个确保具有近乎相等的通道的电路产生不可区分混淆的假设。

主要贡献与结果

为峰值电路采样提供严谨基础：本文首次为“峰值电路”概念提供了严谨的密码学实现。它用精确的 qiO 保证取代了启发式的不可区分性，在假设 $BQP \not\subseteq i.o.BPP$ 和存在 qiO 的条件下，实现了两消息、可公开验证的量子性证明。
无需单向函数的私密 CVQC：作者构建了一个仅使用 qiO 即可对任意 BQP 判定问题进行私密经典验证的协议。这是 qiO（量子）在非平凡密码学应用中的罕见案例，因为它不依赖于额外的计算硬度假设（如 LWE 或陷阱门函数）。
标准模型下的公开 CVQC：他们提出了第一个在标准模型下（不依赖理想化预言机）实现 BQP 计算经典验证的公开验证协议，假设存在 qiO 和后量子 OWF。
qiO 的理论路径：论文将 qiO 的密码学应用与其构建过程进行了分离。它提供了一条通过局部混合框架构建 qiO 的条件路径，将 CCMR 的经典结果扩展到了量子领域。

意义与主张

本文声称为此前仅停留在启发式阶段的量子优势提案提供了严谨的密码学基础。通过将安全性锚定在 qiO 上，研究重心从破解特定的电路构造转向了更广泛、更成熟的混淆问题。

关于构建的谦逊态度：作者明确指出他们并未提供 qiO 的具体实例化。相反，他们提供了一个框架（局部混合归约），使候选构建方案可以在其中进行研究和攻击。
验证范围：其经典验证结果专门针对 BQP 判定问题（是非题），而非通用的采样或关系问题。
盲性 (Blindness)：私密验证协议是“计算盲”的，这意味着证明者除了电路的形状之外，无法获知有关特定实例或答案的任何信息。公开验证协议会揭示答案，但会隐藏特定的实例。
假设层级：这项工作理清了假设的图谱：
- 私密 PoQ 和私密 CVQC 仅需要 qiO 和 $B \not\subseteq i.o.BPP$ 。
- 公开 PoQ 和公开 CVQC 额外需要后量子 OWF（本文证明这些在 PoQ 背景下是“免费”的，因为它们由 PoQ 假设所蕴含）。

总之，本文确立了：如果量子不可区分混淆存在，那么高效、可验证的量子优势和量子计算的经典验证便是可能的，这为衡量量子计算机性能提供了一种新的理论范式。