💻 computer science

Succinct Arguments for QMA in the Quantum Random Oracle Model

本文提出了第一个在量子随机预言模型下针对 QMA 的简洁论证，该论证完全依赖于无结构硬度，通过一种利用针对量子态的可提取向量承诺的新型“承诺-打开”范式，将公开查询健全的量子交互式预言证明转化为量子论证。

原作者： Alessandro Chiesa, Zihan Hu

发布于 2026-09-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Alessandro Chiesa, Zihan Hu

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

在现代计算的广阔版图中，存在着一种持久的张力：机器的力量与人类验证其工作能力之间的矛盾。想象一台超级计算机能在几秒钟内解决一个问题，而这项任务若由人类来检查则需要一辈子的时间。为了信任答案，我们需要一种方法，在不重新进行整个计算的情况下验证结果。这就是简洁论证（succinct arguments）的领域，这是一种密码学工具，它允许验证者以极小的通信量来检查一个主张，这种通信量远小于生成该主张所需的努力。对于通过简单的开关（on-off switches）处理信息的经典计算机而言，这个问题已基本通过使用像哈希函数（hash functions）这样作为数字指纹的基础、无结构化工具得到了解决。然而，下一代计算有望基于量子原理运行，在量子原理下，信息以微妙的叠加态存在，从而实现一种不同的处理能力。长期以来悬在这一领域上空的疑问是：这些同样的简单、无结构化的工具是否也能验证量子计算机的工作，还是说量子世界的复杂性要求全新的、更复杂的密码结构。

来自 EPFL 的一个研究小组现在通过构建首个仅依赖于无结构化难度的量子验证简洁论证，回答了这个问题，该研究是在被称为量子随机预言机模型（quantum random oracle model）的理论框架内完成的。他们的工作表明，理想化的哈希函数不仅对于经典验证，而且对于量子领域也是足够的。这与以往的方法有着显著不同，以往的方法要么需要高度结构化且复杂的密码学假设，要么依赖于关于量子复杂性本质的未经验证的猜想。通过证明经典密码学的基本构建模块可以扩展到量子系统，研究人员表明，验证量子计算的路径比之前认为的更加直接且稳健。

他们成就的核心是一种将量子交互式预言机证明（quantum interactive oracle proof）转化为简洁论证的新方法。要理解这一点，必须首先将量子交互式预言机证明想象成证明者（prover）与验证者（verifier）之间的一场对话。在这场对话中，证明者持有海量的量子数据，即“见证”（witness），而验证者想要检查这些数据是否有效。由于发送整个数据集是不可能的，证明者以一种创建简短、唯一摘要的方式对数据进行承诺。随后，验证者提出特定的问题，而证明者仅提供回答这些问题所需的少量数据片段。量子世界的挑战在于，验证者的提问可能是以叠加态进行的，这意味着他们在同时询问许多位置，而由于量子力学的定律，证明者不能简单地复制数据以保留关于被询问内容的记录。

为了解决这个问题，研究人员开发了一种精密的“承诺并开启”（commit-and-open）编译器。这个系统充当了一个翻译器，将复杂的、多轮的量子对话压缩成一种高效的论证。他们在工作中一个关键的创新是创建了一种新型的量子态承诺方案。在经典计算中，承诺方案就像一个密封的信封：你把消息放进去，封好，稍后你可以打开它以证明里面的内容。在量子世界中，研究人员必须设计一种方案，不仅能密封消息，还能允许证明者相干地抹除自己关于哪些特定部分被开启的记忆，并在验证者返回之前使用过的部分时恢复原始状态。他们通过构建一种“量子态向量承诺”（quantum state vector commitment）实现了这一点，这种承诺的功能类似于一个数字树状结构，其中每个分支都由随机预言机保护。这种结构允许局部开启，这意味着证明者可以只揭示树的少数叶子节点，而不暴露整个结构，同时保持整个系统的完整性。

研究人员证明了这种新系统是可提取的（extractable），这意味着如果恶意证明者试图提交无效证明，一种特殊的算法可以从其承诺中提取出真实的底层量子态。这一特性对于安全性至关重要；它确保了证明者无法在没有实际拥有正确量子见证的情况下伪造有效证明。通过将这种可提取承诺与已知的量子交互式预言机证明相结合，他们创建了一个通信成本随问题规模呈对数增长的协议。这意味着即使对于大规模的量子计算，用于验证结果的交换数据量仍然保持在很小且可控的范围内。

这一结果的意义在于其简洁性以及对最小假设的依赖。以往尝试验证量子计算的方法需要复杂、结构化的密码学原语，这些原语难以实现和分析。通过证明仅靠无结构化难度就已足够，研究人员消除了实现量子验证的一个主要障碍。他们的工作确立了理想化的哈希函数（它们已经是经典安全性的支柱）足以保障量子未来。这一发现解决了该领域一个长期存在的开放性问题，证实了验证量子主张所需的工具在本质上并不不同于用于经典主张的工具，而是需要一种新的方式来应用它们以应对量子态的独特属性。其结果是一种稳健、高效且在理论上可靠的方法，用以确保量子计算的完整性，为更安全、更可信的量子技术铺平了道路。

技术摘要：QROM 中 QMA 的简洁论证

问题陈述

简洁论证（Succinct arguments）是一种密码学原语，允许验证者以显著小于直接验证成本的通信复杂度来检查计算性声明。在经典设置中，针对 NP 的简洁论证已经非常成熟，并且可以通过利用概率可检验证明（PCP）或交互式预言证明（IOP）通过承诺-打开范式（commit-and-open paradigm），仅基于“无结构化”的硬度假设（例如哈希函数）来构建。

然而，将这些结果扩展到涉及量子见证者的 QMA（Quantum Merlin-Arthur，量子类 NP）仍是一个悬而未决的挑战。先前的 QMA 简洁论证构建依赖于以下两种方式之一：

有结构化的密码学假设（例如，基于格的硬度、无知状态准备）。
未经证实的复杂度猜想，特别是量子 PCP（QPCP）猜想，该猜想假设存在具有常数查询复杂度的高效量子证明。

本文探讨的核心问题是：能否仅基于无结构化硬度（如哈希函数）来构建 QMA 的简洁论证，而不依赖于有结构的假设或 QPCP 猜想？

方法论

作者在**量子随机预言模型（QROM）**中提出了一个解决方案，在该模型中，所有参与方都拥有对均匀采样随机预言的量子访问权限。他们的方法将经典的承诺-打开范式推广到了全量子设置。该方法由三个主要的的技术支柱组成：

1. 量子交互式预言证明 (QIOPs)

作者定义了一个稳健的**量子交互式预言证明（QIOPs）**模型。与标准的量子交互式证明（QIPs）不同，QIOPs 允许验证者对其证明消息寄存器进行“局部”查询。为了支持承诺-打开编译，作者为 QIOP 模型引入了特定的特性：

叠加查询（Superposition Queries）： 验证者可以在叠加态下查询证明者寄存器。
返回证明预言（Returning Proof Oracles）： 验证者可以将之前提交的证明寄存器返回给证明者，以便在后续轮次中使用（这对于多轮交互至关重要，因为证明者无法克隆状态）。
公开查询健全性（Public-Query Soundness）： 一种为 QIOPs 形式化的新安全概念。它要求即使验证者的查询位置（可能处于叠加态）在每次查询前后立即泄露给恶意证明者，健全性依然成立。这在编译后的论证中是必要的，因为证明者必须获知查询位置才能提供打开（openings）。

2. 可提取量子状态向量承诺 (QSVC)

为了将 QIOP 编译为简洁论证，证明者必须承诺一个长量子状态，随后打开验证者查询的特定位置。作者发现，由于以下原因，标准的向量承诺在量子设置中是不充分的：

相干打开（Coherent Openings）： 如果查询位置处于叠加态，证明者保留的寄存器将与验证者的位置寄存器发生纠缠。如果没有对“路径信息”（which-path information）进行相干擦除，协议将会失败。
状态恢复（State Recovery）： 当验证者返回一个证明预言时，证明者必须从简洁的承诺中恢复底层的更新量子状态。

为了解决这些问题，作者在 QROM 中定义了可提取量子状态向量承诺（QSVC）。其定义包括：

更新程序（Update Procedure）： 允许诚实的证明者在打开后相干地擦除查询位置的记录。
恢复程序（Recover Procedure）： 允许证明者在承诺被返回时恢复底层的量子消息。
在线可提取性（Online Extractability）： 一个强大的安全概念，其中提取器在获得压缩后的预言数据库后，可以在证明者选择打开之前在线恢复承诺的量子状态，并随后验证打开操作。这使得从论证的健全性到底层 QIOP 的公开查询健全性的直接线性归约成为可能。

3. 构造与编译

作者使用**量子状态树承诺（QSTC）**构建了一个可提取的 QSVC。它结合了 Merkle 树结构与基础的可提取简洁量子状态承诺。该基础承诺在消息寄存器的计算基和 Hadamard 基上同时评估随机预言。提取器使用压缩预言技术相干地恢复原像，将打开验证与 EPR 类型的一致性测试联系起来。

最后，他们提出了一个变换（transformation），可以将任何公开查询 QIOP 编译为 QROM 中的简洁量子交互论证。该变换保持了底层证明系统的效率。

核心贡献

首次实现基于无结构化硬度的 QMA 简洁论证： 本文构建了第一个在 QROM 中仅依赖于随机预言（理想化的无结构化硬度）而非结构化假设或 QPCP 猜想的 QMA 简洁论证。
形式化公开查询 QIOPs： 作者形式化了 QIOPs 的公开查询健全性概念，捕捉了即使查询位置在叠加态下泄露给证明者时，健全性仍需成立的要求。
可提取 QSVCs： 他们定义并构建了具有局部打开、Update 和 Recover 程序的可提取量子状态向量承诺。这一原语对于量子密码学具有独立的价值。
效率保持编译器： 他们提供了一个编译器，可将任何公开查询 QIOP 转换为简洁的量子交互论证，并保持了底层证明系统的轮数和通信复杂度（仅差对数因子）。

结果

主要结果总结如下：

定理 1： 在 QROM 中，存在一个用于 QMA 的简洁量子交互论证，其通信复杂度为 $poly(\lambda, \log \nu)$ ，其中 $\nu$ 是实例规模， $\lambda$ 是安全参数。
定理 2（非正式）： 存在一个变换 $T$ ，可将具有轮数复杂度 $k$ 、证明长度 $l$ 、查询复杂度 $q$ 以及验证者-证明者间通信量 $vc $的 QIOP 编译为具有通信复杂度$ O(\lambda k + \lambda q \log l + vc) $的量子交互论证。其健全性误差为$ O(s_{pq} + k \cdot poly(t, l, q) \cdot 2^{-\lambda}) $，其中$ s_{pq}$ 是 QIOP 的公开查询健全性误差。
定理 3（非正式）： 他们构建了一个在 QROM 中的可提取 QSVC，其提取误差 $\xi_{Ext} = O(t^3 \cdot poly(n, \lambda) \cdot 2^{-\lambda})$ ，针对 $t$ -查询量子对手。
推论 8.3： 通过使用 [SV26] 中最近的高效 QMA QIOP（该 QIOP 满足公开查询健全性）来实例化编译器，作者得到了一个具有多对数（polylogarithmic）轮数复杂度和总通信复杂度为 $poly(\log \nu, \lambda)$ 的 QMA 简洁论证。

意义与主张

本文声称解决了 [BLM26] 提出的关于仅基于无结构化硬度实现 QMA 简洁论证的可行性问题（在预言模型内）。

统一 NP 与 QMA： 该结果表明，理想的哈希函数（由随机预言建模）不仅足以用于 NP 的简洁论证，也足以用于 QMA。
独立于 QPCP： 与以往需要未解决的 QPCP 猜想的方法不同，本构造依赖于已知的有效 QIOPs（特别是 [SV26]）和 QROM。
技术新颖性： 该工作引入了第一个从承诺中“在线”提取量子状态的框架，处理了叠加查询和状态恢复的复杂性，而这些问题在以往的简洁论证背景下尚未得到解决。

作者指出，虽然其结果是在 QROM 中，但在标准模型（来自坍缩哈希函数）中建立类似的结果正在由独立的并行工作处理。他们的贡献具体在于 QROM 中的构造以及可提取 QSVC 原语和公开查询 QIOP 编译器的开发。