⚛️ quantum physics

Unitary complexity in polynomial space

本文为酉复杂度类 $\mathsf{unitaryP}$ 和 $\mathsf{unitaryPSPACE}$ 引入了鲁棒的定义，并证明了量子承诺的存在性意味着酉合成问题的困难性或 $\mathsf{BPP} \neq \mathsf{NEXP}$ 的分离，从而将量子密码学假设与经典复杂度理论中的重大开放问题联系起来。

原作者： William Kretschmer, Ewin Tang

发布于 2026-10-05

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： William Kretschmer, Ewin Tang

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

在计算领域，存在着一个根本性的分歧：即机器能够快速完成的任务与在拥有大量内存的情况下能够完成的任务之间的区别。几十年来，计算机科学家们一直在绘制这些领域的版图，为容易解决的问题、难以解决的问题以及似乎在任何合理时间内都无法解决的问题创建了类别。该领域的一个核心问题是：使用更多内存的能力是否允许计算机解决那些对于内存有限的计算机来说绝对无法触及的问题。虽然我们对答案有着强烈的直觉，但其中许多问题仍未得到证实。

与这个经典世界平行的是量子计算领域，在这里，机器利用亚原子粒子的奇异特性来处理信息。这里的规则不同。量子计算机不仅仅是切换比特的开或关；它操纵的是复杂的概率波。这使得它能够执行某些任务，而这些任务对于经典计算机来说可能需要永恒的时间。然而，一个深刻的谜团一直存在：量子计算的力量是否依赖于一种全新的“硬度”，或者它本质上只是一个伪装成高效版本的经典计算？具体而言，研究人员一直在思考，量子计算机可以执行的所有操作，是否都可以分解为一系列步骤，使得经典计算机在获得适当提示的情况下最终能够理解。如果答案是肯定的，那么量子密码学的独特力量可能只是一种幻觉。如果答案是否定的，那么量子计算机就拥有一种经典机器永远无法复制的根本优势。

两位研究人员，威廉·克雷奇默（William Kretschmer）和伊温·唐（Ewin Tang），最近在解决这一不确定性方面迈出了重要一步。他们并没有完全解开这个谜团，但他们构建了一座强大的逻辑桥梁，将安全量子密码学的存在与经典计算机科学中最古老、最顽固的一些未解问题联系了起来。他们的工作表明，如果现实世界中存在安全的量子密码学，那么以下两种情况之一必将成立：要么我们翻译量子操作为经典指令的能力存在根本限制，要么一个关于经典计算机能力的特定且存在数十年的问题必须有一个令人惊讶的答案。

要理解他们的成就，必须首先掌握他们正在分析的任务的本质。想象一下，量子计算机是一个可以以完美可逆的方式旋转一个复杂多维物体的设备。“酉合成问题”（unitary synthesis problem）询问的是，对于任何这样的旋转，我们是否可以找到一组标准计算机可以遵循的经典指令来重现该旋转。如果我们总能做到这一点，这意味着量子世界在某种意义上只是一个非常复杂的经典世界。研究人员专注于这些旋转中的一类特定旋转：即量子计算机可以使用合理的内存执行的旋转。他们询问，这些特定的旋转是否总能通过一个经典计算机在辅助一个“预言机”（oracle）的情况下进行合成，预言机本质上是一个可以瞬间回答特定问题的神奇黑盒。

作者首先解决了一个实际障碍：如何精确定义这些量子任务。以往的尝试导致了混乱的结果，部分原因是它们允许在计算过程中留下“垃圾”信息。在量子计算中，当机器执行计算时，它经常会留下不再需要但又不能简单删除以免干扰结果的额外数据。一些定义允许这种杂乱的残留数据，而另一些则要求过程完美无瑕。克雷奇默和唐证明了，对于涉及大量内存的任务，这种区别并不重要。他们证明了任何带有垃圾信息的杂乱量子过程都可以转换为一个干净、无垃圾的量子过程，而不会改变任务的根本难度。这是至关重要的一步，因为这使他们能够以一种此前所缺失的数学清晰度来处理这些复杂的量子操作。

有了这些定义，他们开始应对核心问题。他们论证了，对于任何可以用多项式空间（可控的内存量）执行的量子操作，只有两种可能性。要么该操作极其复杂，以至于没有任何经典计算机，无论多么聪明或从预言机那里获得多少帮助，都无法高效地合成它。要么该操作并没有那么难；如果允许经典计算机询问一类被称为 NEXP 搜索问题的特定难题，它就可以被高效合成。第二类问题在经典复杂度理论中是一个极高的门槛，代表了比我们目前已知能解决的最难问题还要难指数级的问题。

这些发现的影响是深远的，特别是对于密码学的未来。量子密码学依赖于这样一个观点：某些任务（例如创建一种“承诺方案”，即一种将秘密锁定在数字盒子中使其既不能被更改也不能被窥探的方法）对于攻击者来说是无法破解的。如果安全的量子承诺存在，那么研究人员的逻辑推导指出，我们正处于一种非常特定的情况中。要么酉合成问题是一个负面答案，意味着存在经典合成无法触及的量子操作，要么一个主要的经典复杂度问题必须得到解决。具体而言，这将意味着 BPP 类问题（可以通过随机性快速解决的问题）不等于 NEXP（可以通过指数时间与非确定性解决的问题）。这是一个存在了四十多年的开放性问题。

简单来说，论文认为，证明安全量子密码学的存在不仅仅是制造更好量子设备的问题。它与经典计算最深刻的理论极限密不可分。如果我们能无条件地证明量子承诺是安全的，我们将同时被迫回答两个长达数十年的巨大谜题之一。我们要么必须接受量子操作在本质上比我们想象的更难被模拟，要么必须证明一种特定且极其强大的经典计算能力严格强于标准的随机计算能力。

这项工作也阐明了量子与经典力量在更广泛意义上的关系。作者表明，如果我们假设酉合成问题具有正面答案（即一切皆可合成），那么具有大内存的量子计算机的力量将受到经典计算机解决 NEXP 搜索问题能力的严格约束。这表明，如果量子计算的“魔力”确实存在，它并不是一种漂浮的现象，而是深深植根于经典复杂度的结构之中。如果量子计算机能做一些真正新颖的事情，那是因为它们正在访问一个经典计算机即使拥有最好的捷径也无法触及的难度层级。

最终，这项研究并不会告诉我们量子密码学是否安全，也不会告诉我们酉合成问题是否可解。相反，它描绘了这两个可能性之间的地形图。它揭示了通往证明量子系统安全性的道路，被那些阻挡了半个世纪以来经典复杂度理论家解决其最难问题的墙壁所阻隔。论文表明，我们不能仅仅通过建设来获得证明；我们必须首先理解计算本身的根本极限。通过澄清定义并建立这些严密的联系，克雷奇默和唐提供了一个更清晰的景观视图，展示了量子密码学的命运与经典复杂度理论的命运是如何以一种此前未被理解的方式紧密结合在一起的。

技术摘要：多项式空间内的酉复杂度

问题陈述
本文探讨了量子密码原语（特别是量子承诺方案）的基础复杂度，及其与经典复杂度理论的关系。由于经典密码学依赖于 $P \neq NP$ 的硬度假设，而近期的预言机分离结果表明，即使在 $P = NP$ 的情况下，量子密码学也可能存在。这引出了“微型密码学”（Microcrypt）范式，即将量子承诺视为量子密码学的最小原语。然而，支撑这些承诺的计算复杂度理论基础仍不明确。

一个核心的未解问题是酉合成问题（由 Aharonov 和 Knill 在 2007 年提出）：是否存在一个多项式时间量子算法，能够在给定经典预言机的情况下实现任何 $n$ 量子比特的酉变换 $U$ ？若该问题有正向解，则意味着酉实现的超多项式下界将导致经典函数的超多项式硬度。反之，负向解可能无法直接为特定密码方案的硬度提供信息。

作者旨在利用经典复杂度技术，探测 unitaryPSPACE（在多项式空间内可实现的酉变换）的计算硬度，具体研究酉复杂度类、酉合成问题以及经典下界之间的关系。

方法论与定义
论文首先指出，现有酉复杂度类定义（特别是 Bostanci 等人 [BEMPQY26] 和 Zhandry [Zha25] 的定义）存在显著的概念缺陷。主要问题包括：

误差缩放（Error Scaling）： 先前的定义通常使时间/空间随 $1/\epsilon$ （误差的倒数多项式）缩放，这导致在复合运算时出现病态行为（例如，无法满足自低性/self-lowness），并允许通过相位编码将难题“走私”进低复杂度类中。
垃圾处理（Garbage Handling）： 定义在实现过程必须将辅助量比特恢复至零态（无垃圾/garbage-free）还是允许任意垃圾态方面存在差异。

为了解决这些问题，作者基于第一原理提出了新的、严谨的 unitaryP 和 unitaryPSPACE 定义：

误差缩放： 复杂度必须随 $\log(1/\epsilon)$ 进行多项式缩放，而非 $1/\epsilon$ 。这确保了在复合运算下的鲁棒性，并与 Solovay-Kitaev 定理保持一致。
无垃圾 vs. 投影（Garbage-Free vs. Projective）： 作者定义了两个类别：
- unitaryP/unitaryPSPACE： 实现必须是“干净的”（辅助量重置为 $|0\rangle$ ），并保持全局相位。
- projUnitaryP/projUnitaryPSPACE： 实现可以产生垃圾（辅助量处于状态 $|g\rangle$ ），实际上忽略了全局相位（投影酉群）。
预言机访问： 预言机提供对一个酉变换 $U$ 及其同态（ $U^\dagger, U^*, U^T$ 以及受控版本）的访问，以确保可组合性。

主要贡献与结果

定义等价性（时间与空间）：
- 作者证明了“干净”定义与“垃圾”定义之间存在深刻联系。具体而言， $U \in \text{projUnitaryP}$ 当且仅当 $U \otimes U^\dagger \in \text{unitaryP}$ 。
- 至关重要的是，对于多项式空间，作者证明了一个更强的结果：UnitaryPSPACE 可以通用地擦除垃圾。他们证明对于每个 $U \in \text{projUnitaryPSPACE}$ ，都存在一个 $V \in \text{unitaryPSPACE}$ 使得 $U = \phi V$ （其中 $\phi$ 是全局相位）。这是通过通过矩阵元可计算性来表征 unitaryPSPACE 实现的：一个酉变换属于 unitaryPSPACE，当且仅当其矩阵元可以在多项式空间内被精确到任意精度。
- 对比： 这种垃圾擦除属性在相对于酉预言机时失效，因为拓扑障碍阻止了全局相位的连续分配。
主要二分法（引理 1.2 / 引理 7.4）：
论文为任何 $U \in \text{unitaryPSPACE}$ 建立了基本的二分法：
- 要么 $U$ 是酉合成硬的（即 $U \notin \text{unitaryP}^{\text{ALL}}$ ，意味着相对于任何经典预言机，它都无法被高效合成），
- 要么 $U$ 可以高效归约为 NEXP 搜索问题（即 $U \in \text{unitaryP}^{\text{FNEXP}}$ ，其中 FNEXP 表示可以访问 NEXP 问题的见证）。
对密码学与复杂度的意义：
- 定理 1.1： 如果量子承诺（等价于 EFI 对）存在，那么要么酉合成问题没有多项式时间解，要么 $\text{BPP} \neq \text{NEXP}$ 。
- 这意味着，要无条件地证明量子承诺的存在，需要解决以下两个长期悬而未决的复杂度理论问题之一：酉合成问题（已开放 20 多年）或 BPP 与 NEXP 的分离问题（已开放 40 多年）。
- 推论 7.10： 如果存在一个相对于 $\text{unitaryP}^L_{\text{PSPACE}} \neq \text{unitaryPSPACE}^L$ 的经典预言机 $L$ ，那么要么酉合成问题是错误的（ $\text{unitaryP}^{\text{ALL}} \neq \text{unitaryALL}$ ），要么 $\text{NC} \neq \text{NP}$ 。这解释了为什么构建此类预言机一直难以实现。

重要性
该论文声称其定义为酉复杂度理论提供了“鲁棒”且“优雅”的基础，解决了以往关于误差缩放和垃圾处理的不一致性。通过建立 unitaryPSPACE 的逐元素表征，作者展示了空间受限的酉计算与经典复杂度类紧密相连。

其主要意义在于架起了量子密码学、酉合成与经典下界之间的桥梁。作者认为，量子承诺的存在并非孤立存在；相反，证明其存在性将必然涉及对经典复杂度理论的突破（特别是分离 BPP 与 NEXP 或解决酉合成问题）。这项工作表明，如果不解决这些深层的复杂度理论问题，就无法完全理解“微型密码学”。

论文最后指出，虽然在多项式空间内可以实现垃圾擦除，但问题在于在多项式时间内是否可行（即 $\text{unitaryP} = \text{projUnitaryP}$ 是否成立）仍然是一个开放问题，尽管作者给出了相对于酉预言机的否定回答。

类似论文