⚛️ quantum physics

Quantum Pessiland

本文确立了“量子悲观地”（Quantum Pessiland）的存在，即一个 $UP \cap coUP$ 的平均情况硬度与几乎所有量子密码原语及基于采样的量子优势的缺失并存的理论世界，从而证明了若要从特定的复杂度假设中构建某些量子原语，非相对化技术是必不可少的。

原作者： Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa

发布于 2026-09-01

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa

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

在现代计算的版图中，存在着一种关于解决问题的难度与保持秘密的可能性之间的根本张力。几十年来，科学家们一直在绘制不同的计算现实“世界”图谱，以理解什么是可能的。其中一个被称为“悲观之地”（Pessiland）的世界，是一个解决复杂问题通常非常困难，但构建安全数字锁所需的工具却根本不存在的地方。在这个阴郁的情景中，尽管自然界呈现出困难的谜题，但却无法创造出单向函数——即一种易于执行但在没有密钥的情况下无法逆转的数学过程。由于几乎所有的经典加密都依赖于这些单向函数，因此“悲观之地”是一个尽管存在难题，却无法实现安全通信的世界。

然而，量子计算的兴起引入了一个新的复杂层面。量子力学允许奇特的行为，例如叠加态，即一个系统可以同时存在于多种状态之中。研究人员长期以来一直想知道，这种奇异的物理现象是否能将密码学从“悲失之地”的阴郁中拯救出来。量子计算机能否在经典基础缺失的情况下，依然创造出安全的系统？这个问题引导科学家们去探寻是否存在一个量子版本的这种凄惨世界——即一个问题依然难以解决，但即使是最先进的量子加密工具也无法存在的空间。

一组研究人员现在以肯定的回答结束了这个问题。他们通过数学手段构建了一个他们称之为“量子悲观之地”（Quantum Pessiland）的理论世界。在这个世界里，他们证明了即使是配备了被称为“量子建议”（quantum advice）的额外提示的量子计算机，在解决某些问题时依然会感到困难。然而，在同一个世界中，基本的量子安全构建模块却根本无法被制造出来。具体而言，他们证明了在该环境下，不可能创造出某些在视觉上看起来不同、但在任何高效计算机面前都无法分辨的量子态对，而这正是许多量子加密方案的要求。他们还论证了，一种特定类型的量子谜题（作为一种数字锁）无法针对经典攻击者进行安全构建。

为了得出这一结论，研究人员并没有建造一台物理机器或在实验室中运行实验。相反，他们利用一个“预言机”（oracle）构建了一个数学模型，预言机本质上是一个能够瞬间回答特定问题的黑盒。他们设计了这个黑盒，使其包含一系列随机且经过洗牌的列表。在他们的模型中，他们展示了虽然可以给量子计算机提供大量的预计算信息来帮助其解决问题，但它仍然无法破解这些理论谜题的安全性。他们发现的核心在于开发了一种名为“修补引理”（patching lemma）的新数学工具。该工具使他们能够证明，即使攻击者了解黑盒内部进行的部分秘密洗牌信息，他们也无法获得足够的信息来破解系统，因为剩余的未知部分是如此庞大且随机，以至于任何尝试猜测的行为都是徒劳的。

这一发现对于量子安全的未来具有深远的影响。研究人员证明，在他们构建的这个世界里，不仅安全的量子锁失效了，量子计算机在生成随机模式方面超越经典计算机的能力也随之消失了。在这个“量子悲观之地”中，量子计算机在采样随机数据方面并不比经典计算机具有优势。这表明，仅仅依靠数学问题的难度，并不能保证安全量子密码学的存在。它意味着，如果我们想要构建一个拥有不可破解量子加密的未来，我们不能仅仅依赖于“某些问题很难解决”这一假设；我们可能需要寻找一个不同的、更具体的安全基础，使其不会在这一阴郁的理论景观中消亡。

这项研究还探讨了该领域内一个关于“解决问题的难度”与“创造量子优势的能力”之间关系的长期开放性问题。通过展示一个“问题虽难但量子优势不存在”的世界确实可以存在，研究人员证明了证明安全量子系统的存在需要超越标准数学模型的技巧。他们的工作起到了一个警示作用：仅仅因为一个问题很难，并不自动意味着我们可以利用它来构建一个安全的系统。通往安全量子未来的道路比单纯希望数学难度足以阻挡黑客要复杂得多。

技术摘要：量子悲观地 (Quantum Pessiland)

1. 问题陈述与动机

本文探讨了“量子悲观地”（Quantum Pessiland）的存在性，这是一个类比于 Impagliazzo [Imp95] 定义的经典“悲观地”（Pessiland）的理论世界。在经典悲观地中，NP 中的问题在平均意义上是困难的，但 单向函数 (OWFs) 并不存在。由于几乎所有的经典密码学原语都隐含了 OWF [IL89]，因此悲观地代表了一个尽管存在平均情况下的硬问题，但本质上无法实现任何经典密码学的世界。

在量子领域，情况有所不同。近期的研究 [Kre21, MY22, AQY22] 表明，即使在不存在 OWF 的情况下，量子密码学（例如私钥量子货币、密钥加密、数字签名）仍然可以存在，其依赖的是更弱的原语，如伪随机状态生成器 (PRSGs)、单向状态生成器 (OWSGs)、单向谜题 (OWPuzzs) 以及 EFI 对（极远但不可区分对）。

核心问题在于：是否存在这样一个世界，其中 NP（或相关的子类）在平均意义上是困难的，但即便这些较弱的量子密码学原语也不存在？ 如果这样的世界存在，则意味着量子密码学不仅仅是经典密码学的某种放宽，而是需要根本不同的硬度假设，或者或许意味着量子密码学在某些平均情况下的硬度设置中是不可能的。

2. 方法论与技术概览

作者构建了一个相对化世界（一个预言机分离）来证明量子悲观地的存在。他们的方法改编并扩展了 Wee [Wee06] 的经典悲观地构造，后者利用了随机置换预言机和一个 PSPACE 预言机。

2.1 预言机构造

作者定义了相对于以下预言机成立的结果：

经典预言机 ( $O$ )： 由一组均匀随机置换 $\pi = (\pi_1, \pi_2, \dots)$ $π = (π_{1}, π_{2}, \dots)$ 的验证预言机 $V^\pi$ $V^{π}$ 和一个固定的 PSPACE 完全预言机 ( $QBF$ $QB F$ ) 组成。
- $V^\pi(\ell, u, v) = 1$ 当且仅当 $|u|=|v|=\ell$ 且 $\pi_\ell(u)=v$ ，否则为 $0$。
量子预言机 ( $U$ )： 对于 EFI 对的结果，他们引入了一个 Helstrom 预言机（一个幺正预言机），该预言机执行最优测量，以区分由电路生成的量子态，并结合了经典预言机 $V$ 。

2.2 核心挑战：辅助输入

一个显著的技术障碍是排除辅助输入 (auxiliary-input) 原语。在经典设置中，Wee [Wee06] 通过证明如果对一小组“重查询”的预言机值进行硬编码，则任何多项式大小的电路都可以被无预言机电路近似，从而排除了具有辅助输入的 OWF。然而，由于以下两个原因，该技术在量子设置中失效了：

叠加查询： 量子算法以叠加态查询预言机，这使得基于经典输入比例的经典“重查询”概念变得定义不明。
均匀性 vs 非均匀性： 辅助输入量子原语是针对接收无限个硬辅助输入的均匀对手定义的。非均匀的“硬编码”策略（建议）是不够的；对手必须被一个能够学习必要信息的均匀算法所破解。

2.3 补丁引理 (Patching Lemma)（关键技术创新）

为了克服这些障碍，作者引入了 补丁引理 (Patching Lemma)（定理 5.2）。该引理提供了一个均匀的量子多项式时间 (QPT) 提取器 $E$ ，它在给定辅助输入 $x$ 时，可以学习一个“补丁” $\Gamma$ （一个三元组 $(\ell, u, v)$ 的有限集合，其中 $V^\pi(\ell, u, v)=1$ ）。

机制： 提取器运行对手算法 $A$ 直至一个随机查询，测量查询寄存器，并在经典上检查预言机 $V^\pi$ 。如果查询是“正向”的（即 $V^\pi=1$ ），则将其添加到补丁中。
指数矩界限： 关键的洞察在于，虽然对所有 $2^n$ 个辅助输入进行简单的并集界限会导致失败，但“发现”（将元素添加到补丁中）的数量遵循一种分布，其中做出多次发现的概率是指数级小的。通过限制发现数量的 指数矩 (exponential moment)，作者证明了即使在最坏情况输入下，预ло期望的发现数量也是输入长度的线性量 ( $O(n)$ )。这使得补丁可以保持多项式大小，同时在随机置换 $\pi$ 的选择上，对所有输入同时保持不可区分性（概率为 1）。

2.4 硬度证明

平均情况硬度： 他们利用近期关于带量子建议的量子置换反转的紧确界 [ABC+26]，结合 Goldreich-Levin 定理 [KT24, AC02]，证明了即使对于带有量子建议的 QPT 算法，反转置换（或解决相关的搜索问题）仍然是平均意义上困难的。
原语不存在性： 利用补丁引理，他们表明任何候选的辅助输入 OWPuzz 或 EFI 对都可以被“补丁”为一个无预言机版本（或仅使用 PSPACE/Helstrom 预言机的版本）。由于 PSPACE/Helstrom 预言机允许高效的反转或区分，因此原始原语被破解。

3. 主要结果

论文确立了关于量子悲观地存在的两个主要定理：

定理 1.1 (经典预言机)

存在一个经典预言机 $O$ ，相对于该预言机：

硬度： 存在一个语言 $L_O \in UP^O \cap coUP^O$ ，对于带有多项式大小依赖于预言机的量子建议的 QPT 算法而言，在平均意义上是强硬的。（因此， $NP \cap coNP$ 也是硬的）。
搜索硬度： 存在一个全唯一搜索关系 $R_O \in TFUP^O$ ，对于相同的算法类在平均意义上是硬的。
无量子优势： $SampBQP^O = SampBPP^O$ 。因此，不存在基于采样的量子优势。
无密码学： 经典安全的辅助输入单向谜题 (OWPuzzs) 不存在。

定理 1.2 (量子预言机)

存在一个量子幺正预言机 $U$ 和一个经典预言机 $V$ ，相对于它们：

硬度： $L_V \in UP^V \cap coUP^V$ 和一个关系 $R_V \in TFUP^V$ 对于带有量子建议的 QPT 算法在平均意义上是硬的。
无密码学： 辅助输入 EFI 对不存在。

推论

推论 1.3： 相对于经典预言机， $PP$ 对于带有量子建议的 QPT 算法是强平均意义下硬的，然而 OWPuzzs 并不存在。这暗示了 $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$ 。
推论 1.4： 相对于经典预言机，尽管 $UP \cap coUP$ 具有平均情况下的硬度，但无效验证者量子性证明 (IV-PoQ) 不存在。

4. 意义与影响

本文声称具有以下意义：

量子悲观地的存在性： 它证明了存在这样一个世界，其中平均情况下的硬度存在（特别是对于 $UP \cap coNP$ ），但没有任何量子密码学（无论是经典安全还是量子安全的 OWPuzzs 和 EFI 对变体）是可能的。这与经典情况形成对比：在经典情况下，OWF 的不存在意味着所有经典密码学的不存在，但在本文中，即使 $UP \cap coUP$ 是硬的，量子原语的不存在性也被展示了出来。
量子优势的极限： 该世界中的结果 $SampBQP = SampBPP $表明，仅凭$ UP \cap coUP$ 的平均情况硬度不足以保证基于采样的量子优势。
技术分离： 本文处理了一个关于从 $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$ 构建 OWPuzzs 的开放问题。由于尽管该分离成立，但在其预言机世界中 OWPuzzs 并不存在，作者得出结论：若要仅从该复杂度理论假设构建 OWPuzzs，非相对化证明技术 (non-relativizing proof techniques) 是必要的。这为 Khurana 和 Tomer [KT25] 提出的开放问题提供了一个部分否定回答。
技术进步： 补丁引理 (Patching Lemma) 被呈现为 Wee 逼近引理的一个均匀的量子模拟，专门设计用于处理存在叠加查询时的具有辅助输入的均匀对手。

作者保持了谦逊的态度，指出其结果是相对于预言机的，并不解决在非相对化（真实）世界中是否存在这样一个问题的疑问。他们强调，其工作旨在澄清在相对化设置中平均情况硬度与量子密码学原语存在性之间的分离关系。