⚛️ quantum physics

Separating Quantum and Classical Advice with Good Codes

本文通过结合 Yamakawa-Zhandry 提出的代码交集问题与具有极佳列表恢复性质的编码，构建了一个无条件经典预言机，首次证明了量子证明类（QMA）与经典证明类（QCMA）之间的分离，并进一步实现了量子建议类（BQP/qpoly）与经典建议类（BQP/poly）之间的无条件经典预言机分离，其证明方法比现有工作更为简洁且易于推广。

原作者： John Bostanci, Andrew Huang, Vinod Vaikuntanathan

发布于 2026-04-14

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： John Bostanci, Andrew Huang, Vinod Vaikuntanathan

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

这篇论文解决了一个计算机科学中非常深奥的问题：量子计算机拥有的“量子提示”（Quantum Advice）是否比“经典提示”（Classical Advice）更强大？

为了让你轻松理解，我们可以把计算机解决问题想象成**“在迷宫中找出口”**。

1. 核心角色与背景

想象有两个侦探，都在试图解开一个巨大的迷宫谜题（这是一个复杂的数学问题）：

侦探 A（经典侦探）： 他手里拿着一张纸质地图（经典提示）。这张地图是用 0 和 1 写成的，非常具体，但信息量有限。
侦探 B（量子侦探）： 他手里拿着一块神奇的量子水晶球（量子提示）。这块水晶球里包含着一种“叠加态”的信息，它似乎能同时指向迷宫的许多条路径。

核心问题： 如果给这两个侦探同样的时间，侦探 B 手里的“量子水晶球”是否真的比侦探 A 的“纸质地图”更厉害，能解开更多侦探 A 解不开的谜题？

在计算机科学里，这对应着两个复杂的类：

BQP/poly：有经典提示的量子计算机。
BQP/qpoly：有量子提示的量子计算机。

之前的研究已经证明，在某些特殊的、人造的“魔法迷宫”（量子预言机）里，量子水晶球确实更强。但科学家们一直想知道：在普通的、大家都能理解的“经典迷宫”里，这种优势还存在吗？ 这就是这篇论文要回答的问题。

2. 他们的“魔法迷宫”是什么？（代码交集问题）

作者设计了一个非常巧妙的迷宫，叫做**“代码交集问题”**。

迷宫的构造： 想象有一本巨大的密码书（代码），里面写满了成千上万个合法的“密码串”（比如 10110...）。
任务： 给你一串乱码（哈希值），让你从密码书里找出一个合法的密码串，使得它经过某种变换后，正好等于这串乱码。
难点： 密码书太大了，乱码又太随机，找起来像大海捞针。

为什么量子侦探能赢？
量子侦探可以利用“量子水晶球”（量子提示），这个水晶球里预先编码了所有密码串和它们对应的变换关系。通过一种叫“量子傅里叶变换”的魔法（就像把一团乱麻瞬间理清），他能瞬间锁定那个正确的密码串。

为什么经典侦探会输？
经典侦探只能拿到一张纸（经典提示）。这张纸虽然也包含信息，但根据**“不可克隆定理”**（量子力学的一个基本法则，就像你不能完美地复印一个未知的量子状态），经典侦探无法把量子水晶球里的“叠加信息”完美地压缩成一张纸。
如果经典侦探试图通过“猜”或者“试错”来找到密码，他需要尝试的次数是天文数字，根本来不及。

3. 他们是怎么做到的？（三个关键创新）

以前的研究虽然证明了量子优势，但用的方法非常复杂，像是一台精密的瑞士钟表，稍微动一下齿轮就坏了。这篇论文做了一些“简化”和“升级”：

A. 使用“超级纠错码”（多重重码）

以前的迷宫设计用的是一种普通的“折叠 Reed-Solomon 码”，就像普通的迷宫，虽然难走，但经典侦探如果运气好或者提示给得够多，还是能蒙对的。
这篇论文换用了**“多重重码”（Multiplicity Codes）。这就像是一个超级迷宫**，它的结构非常特殊，具有极强的“列表恢复”能力。

比喻： 想象普通迷宫里，你走错一步可能只是多绕个圈；但在超级迷宫里，你走错一步，周围所有的路都会把你引向死胡同，除非你拥有极其精确的“量子导航”。这种结构让经典侦探几乎不可能通过“猜”来蒙对答案。

B. 引入“有偏见的”随机性（作弊的迷宫）

以前的迷宫是完全随机的，像扔骰子。但这篇论文设计了一个**“有偏见”的迷宫**。

比喻： 想象迷宫的墙壁大部分是白色的，只有少数是黑色的。量子侦探利用这个“白色占多数”的特点，可以极大地减少需要解码的“噪音”，就像在雪地里找黑点比在黑白混杂的森林里找黑点容易得多。
这使得量子侦探能更轻松地利用他的水晶球找到答案，而经典侦探因为无法利用这种结构性的“偏见”，依然被困在迷雾中。

C. 从“证明”到“建议”的跨越

这篇论文不仅解决了“谁能证明答案”（QMA vs QCMA）的问题，还解决了“谁能利用建议”（BQP/qpoly vs BQP/poly）的问题。

之前的困境： 证明问题中，侦探可以针对每个具体问题拿不同的提示；但在建议问题中，提示必须是通用的，要能解决所有同类问题。
突破： 作者发现，如果经典侦探试图用一张纸（经典建议）来模拟量子水晶球的功能，他必须“猜”出大量密码串。由于密码串的数量是指数级的，而纸的容量是有限的，经典侦探注定会失败。这就好比让你用一张便利贴去描述整个互联网的所有网页，这是不可能的。

4. 结论：这意味着什么？

这篇论文给出了一个无条件的、基于经典迷宫的分离证明。

简单来说： 即使我们限制在大家都熟悉的经典计算机模型下（使用经典预言机），量子计算机如果拥有“量子提示”（量子水晶球），其能力确实严格强于拥有“经典提示”（纸质地图）的量子计算机。
意义： 这不仅仅是理论上的胜利，它告诉我们，量子信息中有一些本质上的、无法被经典信息压缩的特性。这种特性不是因为我们还没找到更好的算法，而是物理定律（量子力学）本身决定的。

一句话总结：
作者设计了一个极其精妙的“超级迷宫”，证明了量子计算机手里的“量子水晶球”能瞬间找到出口，而经典计算机手里的“纸质地图”无论怎么努力，都只能在这个迷宫里打转。这证实了量子提示拥有经典提示永远无法企及的超能力。

这篇论文《Separating Quantum and Classical Advice with Good Codes》（利用优良码分离量子与经典建议）由 John Bostanci、Andrew Huang 和 Vinod Vaikuntanathan 撰写。该研究在计算复杂性理论领域取得了重要突破，主要解决了两个长期未决的开放性问题：在经典预言机（Oracle）模型下，量子证明（QMA）是否严格强于经典证明（QCMA），以及量子建议（BQP/qpoly）是否严格强于经典建议（BQP/poly）。

以下是该论文的详细技术总结：

1. 研究背景与核心问题

在量子复杂性理论中，以下两个问题长期以来悬而未决：

QMA vs. QCMA: 是否存在一个语言，可以被带有量子证明的量子多项式时间验证器（QMA）高效验证，但无法被带有经典证明的量子验证器（QCMA）验证？
BQP/qpoly vs. BQP/poly: 是否存在一个语言，可以被带有量子建议（量子态）的量子算法（BQP/qpoly）高效解决，但无法被带有经典建议（比特串）的量子算法（BQP/poly）解决？

之前的研究（如 Aaronson 和 Kuperberg, 2007）仅在量子预言机（Unitary Oracle）模型下证明了这些分离。最近的 Bostanci 等人（BHNZ25, STOC 2026）在经典预言机模型下分离了 QMA 和 QCMA，但其证明极其复杂，依赖于“谱傅里叶变换”（Spectral Forrelation）和哈密顿量学习等深奥技术，且未能解决 BQP/qpoly 与 BQP/poly 的分离问题。

本文的目标是提供一个概念上和技术上更简单的经典预言机分离证明，并首次解决 BQP/qpoly 与 BQP/poly 的经典预言机分离问题。

2. 方法论与核心技术

作者提出了一种基于**优良码（Good Codes）的通用构造方法，核心思想是利用码交集问题（Code Intersection Problem）**的变体。

2.1 广义码交集问题 (Generalized Code Intersection Problem)

基本设定：给定一个线性码 $C \subseteq \Sigma^n$ 和一个哈希函数 $H: [n] \times \Sigma \to \{0, 1\}$ ，以及目标哈希值 $x$ 。目标是找到一个码字 $v \in C$ ，使得对于所有 $i$ ，满足 $H(i, v_i) = x_i$ 。
量子优势：Yamakawa 和 Zhandry (2022) 证明了在给定 $H$ 的预言机访问权限下，量子算法可以高效解决此问题（利用量子傅里叶变换和卷积定理），而经典算法无法做到。
挑战：直接使用该问题无法分离 QMA 和 QCMA，因为两者都可以访问 $H$ 的预言机，且该问题本身就在 BQP 中。

2.2 关键创新点

为了克服上述挑战，作者引入了以下三个关键修改：

引入“码交集子集大小”问题 (CISS)：
- 定义了一个新的预言机 $O[H, E]$ ，它不仅检查 $H(v)=x$ ，还检查 $(x, v)$ 是否属于一个特定的集合 $E$ 。
- YES 实例： $E$ 是所有可能的 $(x, v)$ 对的集合。
- NO 实例： $E$ 是一个极小的集合（大小远小于 $2^n$ ）。
- QMA 证明：验证者可以接收一个关于 $H$ 的量子建议状态 $|adv_H\rangle$ （包含 $H$ 的预像叠加态），从而无需查询 $H$ 即可生成满足条件的 $v$ ，进而检查 $O$ 。
- QCMA 下界：如果存在 QCMA 算法，则意味着存在一个经典见证者，可以区分 $E$ 是大还是小。利用混合引理（Hybrid Lemma），可以将 QCMA 算法转化为一个“猜测器”（Guesser），该猜测器在不查询预言机的情况下，能以非忽略概率生成多个满足 $H(v)=x$ 的码字对。
利用优良码的列表恢复性质 (List Recovery)：
- 为了证明经典猜测器无法成功，作者需要证明：如果猜测器生成了 $\ell$ 个不同的码字，那么这些码字覆盖的符号总数 $s(\ell)$ 必须非常大。
- 如果 $s(\ell)$ 很大，那么在没有查询 $H$ 的情况下猜对所有对应符号的哈希值的概率将呈指数级下降。
- 关键选择：作者放弃了之前工作中使用的折叠 Reed-Solomon (FRS) 码，转而使用重数码（Multiplicity Codes）。重数码具有极强的列表恢复性质（List Recovery），即对于任意 $\ell$ 个码字，它们覆盖的符号集大小是 $\Omega(n \cdot \ell)$ 。这保证了经典猜测器的成功概率极低。
偏置预言机 (Biased Oracles) 与低汉明权重限制：
- 问题：重数码的对偶码距离较小，无法处理完全随机的 $H$ 产生的高噪声（即 $H(v)=x$ 的约束会导致大量错误）。
- 解决方案：
  - 偏置 $H$ ：构造 $H$ 使得输出为 0 的概率 $p$ 远大于 1/2。
  - 限制输入：只考虑汉明权重较低的 $x$ （例如 $x$ 后补零）。
  - 效果：这种偏置使得在 $x$ 为低权重时，对偶码解码所需的错误向量汉明权重显著降低（集中在 $n(1-p)$ 附近），从而使得量子算法（Yamakawa-Zhandry 算法的变体）能够成功解码。同时，由于 $H$ 是偏置的，经典猜测器猜对大量符号的概率进一步降低，从而产生矛盾。

3. 主要结果

3.1 QMA 与 QCMA 的分离

定理 1.1：存在一个经典预言机 $\mathcal{O}$ ，使得 $\text{QMA}^\mathcal{O} \not\subseteq \text{QCMA}^\mathcal{O}$ 。
意义：这是继 BHNZ25 之后，第二个无条件经典预言机分离，但证明过程更简单、更结构化。此外，该分离甚至适用于 $\text{NP} \cap \text{coNP} \cap \text{BQP/qpoly}$ 与 $\text{BQP/poly}$ 的分离，表明其结构不同于基于谱傅里叶变换的分离。

3.2 BQP/qpoly 与 BQP/poly 的分离

定理 1.2：存在一个经典预言机 $\mathcal{O}$ ，使得 $\text{BQP}^\mathcal{O}/\text{qpoly} \not\subseteq \text{BQP}^\mathcal{O}/\text{poly}$ 。
突破：这是首个无条件经典预言机分离。之前的分离仅限于量子预言机（Aaronson-Kuperberg）或非标准的“经典可访问经典预言机”模型（Li et al., 2024）。
机制：作者将搜索问题（寻找码字）转化为决策问题。利用 Yao 的盒子问题（Yao's Box Problem）和上述的 CISS 构造，证明了带有经典建议的量子算法无法解决该问题，而带有量子建议的算法可以。

4. 技术细节与证明思路

QMA 算法的构造：
- 利用重数码的对偶码具有良好的距离性质（在偏置 $H$ 和特定输入下）。
- 量子建议状态 $|adv_H\rangle$ 编码了 $H$ 的所有预像的叠加态。
- 验证者利用量子傅里叶变换（QFT）和卷积技巧，结合对偶码的解码器，高效生成满足 $H(v)=x$ 的码字 $v$ 。
QCMA/BQP/poly 的下界证明（反证法）：
- 假设存在成功的经典见证者（或经典建议）。
- 构造一个“猜测器”算法，通过模拟验证器并测量其查询，逐步收集满足条件的 $(x, v)$ 对。
- 利用列表恢复性质：如果猜测器生成了 $\ell$ 个码字，则这些码字在 $\Omega(n \cdot \ell)$ 个位置上覆盖了不同的符号。
- 利用偏置 $H$ ：猜测器必须猜对这些位置上的 $H$ 值。由于 $H$ 是偏置的且猜测器没有查询权限，猜对 $\Omega(n \cdot \ell)$ 个值的概率是 $(1-p)^{\Omega(n \cdot \ell)}$ ，这是一个极小的值。
- 这与猜测器的高成功概率假设矛盾，从而证明不存在这样的经典见证者/建议。

5. 意义与贡献

简化证明：相比 BHNZ25 基于“谱傅里叶变换”的复杂证明，本文基于码理论和列表恢复的证明更加直观、简洁，且易于推广。
解决长期开放问题：首次解决了 BQP/qpoly 与 BQP/poly 在经典预言机模型下的分离问题，填补了量子复杂性理论的重要空白。
新工具的应用：展示了**重数码（Multiplicity Codes）**在量子复杂性分离中的强大作用，特别是其优秀的列表恢复性质，这是之前工作（使用 FRS 码）所不具备的。
结构洞察：揭示了量子证明/建议的优势不仅仅在于处理“随机性”，还在于能够利用量子态的叠加性来编码和提取关于结构化问题（如码字解码）的信息，而经典信息无法做到这一点。
密码学启示：论文讨论中提到，这种分离与“量子货币”和“复制保护软件”等密码学原语有关，可能为构建这些原语提供新的思路。

总结

这篇论文通过巧妙地结合重数码的优良列表恢复性质、偏置预言机以及Yamakawa-Zhandry 算法的变体，在经典预言机模型下成功分离了量子与经典的证明及建议能力。其证明不仅比前人工作更简洁，而且首次攻克了 BQP/qpoly 与 BQP/poly 的分离难题，为理解量子计算相对于经典计算的本质优势提供了新的视角和强有力的证据。