⚛️ quantum physics

A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms

本文建立了一个不可能性定理，证明任何遵循 Regev 傅里叶采样模板的二面体陪集问题量子算法都必须利用几乎所有的傅里叶标签位，从而表明 Simon 最近提出的算法由于仅依赖于这些标签的一个子集，因此无法解决该问题。

原作者： Aparna Gupte, Seyoon Ragavan, Mark Zhandry

发布于 2026-10-01

📖 1 分钟阅读🧠 深度阅读

原作者： Aparna Gupte, Seyoon Ragavan, Mark Zhandry

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

在寂静而高风险的密码学世界中，存在着一场建造锁具者与尝试撬锁者之间的持久竞赛。几十年来，科学家们一直在设计基于复杂几何形状（称为格）的加密系统。这些系统被认为是保护未来数据（即在强大的量子计算机可能存在的未来）的最佳希望，因为其背后的数学问题被认为极其难以解决。其中一种最有可能破解这些锁的方法是解决一个被称为二面体余集问题的特定谜题。这个谜题作为一个关键测试：如果一台计算机能够高效地解决它，它很可能会粉碎我们赖以生存的未来格密码的安全。挑战在于，虽然我们知道如何设置这个谜题，但寻找一种快速解决它的方法仍然是量子计算中最顽固的障碍之一。

最近，一种新方法似乎带来了突破。研究员丹尼尔·西蒙（Daniel Simon）提出了一种方法，似乎绕过了过程中一个极其困难的步骤，承诺能快速解决二面体余集问题。如果这是真的，这将是一个巨大的转变，意味着未来加密的安全可能比预期更早受到威胁。然而，来自麻省理工学院、谷歌量子人工智能和斯坦福大学的研究团队现在对这一说法进行了严格审查，并发现了一个根本性的缺陷。他们证明了所提出的方法以及一类类似的策略都无法奏效。他们的工作建立了一个硬性屏障：要解决这个特定的谜题，量子算法必须保留它收集到的几乎每一件信息。如果它丢弃了哪怕极小比例的数据，解题就会变得不可能。

这一发现的故事始于这些算法是如何设计的。想象一台量子计算机试图寻找一个隐藏的数字，而这个数字就是谜题的密钥。计算机开始生成大量的样本，每个样本都包含一些经典数据和一个微妙的量子态。解决该问题的标准方法由奥德·雷格夫（Oded Reving）多年前建立，涉及一个两步走的舞步。首先，计算机进行测量，从样本中提取出一些信息。其次，它使用一个被称为“预言机”（oracle）的特殊工具来清理剩余的数据并揭示秘密。问题在于，这个特殊工具非常缓慢且效率低下，本质上要求计算机先解决另一个同样困难的谜题，才能取得进展。

西蒙最近的提议旨在跳过这个缓慢的工具。他建议直接处理数据，希望能不通过昂贵的清理步骤就提取出秘密。他的方法涉及对数据进行分组，并进行仅依赖于信息中最显著部分的计算，从而忽略掉那些不太重要的部分。从表面上看，这似乎是一个聪明的捷径。通过丢弃“噪声”或较不关键的细节，该算法有望运行得更快。这是一个诱人的想法：如果你可以通过只观察前三分之一的信息来解决谜题，你就能节省大量的资源和时间。

古普特（Gupte）、拉加万（Ragavan）和赞德里（Zhandry）的新论文表明，这种捷径是一种幻觉。他们证明，对于这种特定类型的量子算法，丢弃信息是致命的。他们的论点建立在对量子信息行为的深刻洞察之上。当计算机收集样本时，不同的数据片段以一种纠缠的方式结合在一起，从而保留了一种微妙的全局模式。这种模式正是最终揭示秘密数字的关键。研究人员证明，如果你从样本中移除哪怕极少量的信息——具体来说，如果你从每件数据中丢弃超过对数级别的比特——那么维持模式的微妙量子连接就会崩塌。

要理解为什么会发生这种情况，请考虑：秘密数字并不存储在任何单一的数据片段中，而是编织在所有数据之间的关系之中。当算法丢弃数据的次要位时，它不仅仅是在移除噪声，它是在切断连接各部分的丝线。研究人员展示了，一旦这些比特消失，剩余的信息就会变得如此混乱，以至于秘密数字实际上被隐藏了起来。在统计学上，区分不同的可能秘密变得不可能。量子态失去了其相干性，算法只剩下一堆杂乱无章的东西，无法提供任何关于答案的线索。

这一发现直接适用于西蒙的算法。作者分析了他的方法的步骤，发现尽管后期阶段非常复杂，但该算法实际上仅依赖于每个数据样本的前三分之一比特。它丢弃了剩余的三分之二，假设这些部分是不需要的。根据新的证明，这正是算法失败的地方。通过扔掉这些比特，算法破坏了解决谜题所需的信息。研究人员计算出，该算法成功的概率微乎其微，实际上几乎为零。即使算法运行多次，它找到正确答案的可能性仍然可以忽略不计。

这一结果对量子计算和密码学领域具有重要意义。它为一类试图通过简化数据来解决二面体余集问题的尝试提供了明确的“禁止通行”（no-go）定理。它告诉研究人员，他们不能采取丢弃信息的简便途径；他们必须找到一种使用他们收集到的全部数据丰富度的办法。这排除了西蒙提出的特定捷径，并表明任何未来试图使用这种模板破解这些格密码的尝试都将面临同样的根本障碍。这些依赖于此问题的加密系统的安全性在这一特定攻击路径下依然完好无损。

作者并未止步于仅仅反驳该算法，他们还为如何成功提供了清晰的指南。他们的工作表明，任何成功的算法都必须保留关于傅里叶标签（即过程中生成的特定数据点）的几乎所有信息。这不仅仅是一个建议，而是一个数学上的必然。如果算法丢弃过多，秘密就会永远丢失。这一洞察力就像一个指南针，引导着未来的研究，使其远离死胡同，转向那些能够保持必要量子相干性的方法。

最后，论文证实了破解这些密码锁的路径比最近的一个提议所暗示的要困难得多。通过这种方式快速、简单地解决二面体余集问题的梦想已被证明是无法实现的。研究人员已经证明，量子可能性的世界受到严格规则的约束：你不能丢弃细节却期望保留整体图景。目前，格密码依然安全，而解决二面体余集问题的探索仍在继续，并在这种“信息丢失是无法逾越的障碍”的新理解指引之下进行。

技术摘要：二面体余集算法中的傅里叶标签信息丢失屏障

问题陈述
本文研究了二面体余集问题（Dihedral Coset Problem, DCP），这是量子计算领域的一个核心挑战，对后量子密码学具有重要意义。Regev [Reg04a] 指出，若存在求解 DCP 的高效量子多项式时间（QPT）算法，将意味着可以高效求解硬格问题（hard lattice problems），从而破坏拟议的基于格的密码系统的安全性。解决 DCP 的主要方法由 Regev 提出，其模板包括傅里叶采样（Fourier sampling）后接子集和测量（subset-sum measurement）。虽然 Regev 最初的构造需要一个子集和问题的预言机（被认为在超多项式时间内），但 Simon [Sim26] 最近的一项声称试图通过在 Regev 模板中移除该预言机来在 QPT 内解决 DCP。本文通过建立对遵循 Revere 模板算法的根本限制，研究了此类声称的有效性。

方法论与框架
作者分析了 Regev 提出的“傅里叶采样与子集和测量模板”。在该框架下：

设置： 算法接收 $m$ 个形式为 $(y, \frac{1}{\sqrt{2}}(|0\rangle + \omega_N^{dy}|1\rangle))$ 的傅里叶样本，其中 $N=2^n$ 是模数， $d \in \mathbb{Z}_N$ 是秘密值， $y$ 是均匀采样的。
步骤 1（拼接）： 算法将 $m$ 个样本进行拼接，形成一个包含经典标签 $y$ 和量子寄存器 $b \in \{0,1\}^m$ 的状态。
步骤 2（子集和测量）： 算法在叠加态中计算 $f_y(b) = \langle y, b \rangle \pmod N$ ，并测量该和的低 $n-1$ 位，记作 $z$ 。剩余的信息是一个量子态，其相位取决于 $f_y(b)$ 的最高有效位以及秘密值 $d$ 。

作者方法论的核心在于分析在步骤 2 之后丢弃傅里叶标签 $y$ 的比特所导致的信息论后果。他们引入了“摘要函数”（digest functions） $H_i: \mathbb{Z}_N \to [K]$ ，将 $y$ 的每个分量映射到较小的输出，从而有效地丢弃信息。本文证明，如果一个算法从每个傅里叶标签 $y$ 中丢弃 $\omega(\log n)$ 比特的信息（即摘要输出大小 $K$ 相对于 $N$ 较小），则该算法将失去区分秘密 $d$ 的最低有效位（LSB）的能力。

主要贡献与结果
本文为遵循 Regev 模板的一类广泛量子算法建立了一个“不可能性定理”（no-go theorem）。

定理 2.1（主要的不可能性结果）： 作者证明，任何遵循 Regev 模板且在测量子集和的低 $n-1$ 位后，通过摘要函数（其输出范围 $K$ 较小）丢弃每个傅里叶标签 $y$ 中 $\omega(\log n)$ 比特信息的 QPT 算法，都无法以非忽略的优势区分 $d$ 的 LSB 为 0 或 1 的情况。具体而言，区分优势被限制在 $m\sqrt{K/N}$ 以内。
- 机制： 该证明依赖于这样一个观察：只有保留完整的傅里叶标签 $y$ （或接近完整）时，恢复 $d$ 所需的量子相干性才能得以维持。 $y$ 寄存器与控制寄存器 $b$ 存在强纠缠。丢弃关于 $y$ 的信息相当于在 $b$ 上施加了一个退相干通道，实际上破坏了包含 $d$ 的相位信息。作者通过证明当丢弃足够的 $y$ 比特时， $d=0$ 和 $d=1$ 对应的状态之间的迹距离变得可以忽略不计，从而形式化了这一点。
对 Simon 算法的应用（推论 2.2）： 本文将该定理应用于 Simon [Sim26] 最近提出的算法。Simon 的算法试图通过计算基于 $y$ 的分块与 $b$ 的内积的特定函数 $g_{y(i)}(b(i))$ 来恢复 $d$ 的 LSB。作者证明，Simon 的算法实际上丢弃了每个傅里叶标签 $y$ 约 $2n/3$ 的最低有效位（仅保留前三分之一）。
- 由于保留的信息构成了一个输出大小为 $K \approx 2^{n/3}$ 的摘要，Simon 算法的区分优势被限制在 $\text{poly}(n)2^{-n/3}$ 。
- 因此，Simon 算法无法高效解决 DCP。作者在注记 2.4 中进一步论证，即使通过后选择（重试与放大），该算法也无法同时实现亚指数级运行时间与反亚指数级正确性。
形式化验证： 为了确保可验证性，作者发布了用于形式化其结果（包括主定理及对 Simon 算法的应用）的 Lean 4 代码。

意义与主张
本文声称为 DCP 的一类特定且广泛的方法提供了确定性的屏障。

驳斥近期声称： 其主要意义在于驳斥了 Simon [Sim26] 解决 DCP 的声称。作者表明，该算法之所以失败，是因为它丢弃了过多的傅里叶标签信息，而这一构造过程中的必要步骤无意中破坏了求解问题所需的相干性。
研究指导： 作者认为其结果可以作为未来算法开发的“有用指南”。该定理暗示，任何遵循 Revere 模板的算法都必须广泛利用傅里叶标签 $y$ ；即使丢弃极小比例的信息（具体为 $\omega(\log n)$ 比特）也会在信息论层面导致失败。
局限性与注意事项： 作者对其结果的范围持谨慎态度。他们承认其不可能性定理专门适用于遵循 Revere 模板（傅里叶采样 + 子集和测量）的算法。他们指出，虽然存在表象上的规避方法（例如，保留 $y$ 寄存器但不使用它们），但这并不能挽救算法的正确性。此外，他们表示尚未发现任何能有意义地绕过定理 2.1 的“真实且合理的修复路径”，尽管他们并不排除在 Revere 模板之外存在完全不同的算法路径的可能性。

总之，本文确立了对于 Revere 模板而言，傅里叶标签不仅是辅助数据，而且是维持解决 DCP 所需量子相干性的必要条件。任何尝试压缩或丢弃这些标签的行为，都会导致一种信息论层面的屏障，使得算法无法成功。

类似论文