⚛️ quantum physics

All Unitaries Have Constant Depth Quantum Circuits

本文证明了，在拥有指数级辅助量子比特的情况下，任何 $n$ 量子比特幺正变换都可以通过使用无限制扇出门（unbounded fan-out gates）的常数深度量子电路，或使用标准门的多项式深度量子电路来达到任意精度的逼近，从而解决了关于通用幺正变换合成是否需要指数级深度的开放性问题。

原作者： Barak Nehoran, Henry Yuen

发布于 2026-10-01

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Barak Nehoran, Henry Yuen

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

在量子计算的世界中，任何计算的基础构建模块是一种被称为幺正变换（unitary operation）的操作。你可以将其想象成一条规则，它告诉量子系统如何在不丢失任何信息的情况下改变其状态，就像一副扑克牌的完美洗牌，既重新排列了卡牌，又保持了卡牌总数不变。科学家们早已知道，对于一个拥有许多粒子的系统，创建这些特定的规则是极其困难的。构建这种规则的标准方法涉及一系列漫长的微小步骤，其步骤数量增长之快，以至于对于即使是复杂度适中的系统，整个过程所需的时间也会超过宇宙的年龄。这导致了一种广泛的观点，即某些量子任务无论投入多少额外的资源或“辅助”粒子，都注定无法快速完成。多年来一直悬而未决的问题是：这种缓慢究竟是物理学中不可打破的定律，还是仅仅是我们目前尝试的方法所带来的局限性。

哥伦比亚大学的一个研究小组现在表明，这种缓慢并非自然法则，而是一种设计选择。他们证明了，只要人们愿意使用大量的辅助粒子，任何可能的量子系统变化规则都可以在出人意料的短时间内完成。他们的工作证明，运行复杂量子计算所需的时间可以与空间进行交换。与其将一系列步骤一个接一个地运行，研究人员发现了一种同时运行所有必要步骤的方法。通过使用海量的额外粒子来进行并行处理，他们将执行这些复杂变换所需的时间从一个不可能的持续时间缩短到了可控的范围内。事实上，他们展示了如果计算机被允许使用一种特殊的强大连接方式——能够瞬间将信息复制到许多地方——那么整个过程可以在一个单一的、恒定的瞬间内完成，无论系统的复杂度如何。

通往这一发现的路径始于对问题的一种不同思考方式。研究人员不再试图一步步构建规则，而是将规则视为编码在数学形状中的隐藏信息。他们意识到，如果能针对这个形状提出正确的问题，就能重建整个规则。这个想法类似于通过从几个不同的角度照射物体来确定物体的形状。研究人员开发出一种方法，向一个持有规则信息的特殊辅助者提出三个特定的问题。这些问题旨在以一种能够揭示规则结构的方式来探测该数学形状。其关键洞察在于使用一种将信息存储在连续、平滑的波状形式中，而非标准计算机使用的离散、开关式比特中的辅助者。这使得他们能够以极高的效率提取必要的信息。

然而，真实的量子计算机无法处理完美的平滑连续波；它们是在离散的步骤中工作的。为了让他们的想法在真实机器上奏效，研究人员必须将他们的平滑数学解转化为使用有限网格点的版本。他们证明，通过选择足够精细的网格，可以用惊人的精度逼近平滑解。这种近似引入的误差如此之小，以至于只需增加几个网格点，就可以使其小于任何预设的极限。这种离散化过程是连接他们优雅的数学理论与实际量子电路的桥梁。其结果是，为量子计算机提供了一套配方，使其能够以随系统规模增长极慢的速度执行任何变换，而不是发生指数级的爆炸式增长。

拼图的最后一块是展示如何利用量子计算机上现有的物理门来构建这个配方。研究人员将他们的算法分解为三个主要部分：准备初始状态、向辅助者提出三个问题，然后读取结果。他们证明了其中的每一个部分都可以仅通过粒子之间的简单、标准连接来构建。至关重要的是，他们展示了这些连接可以被排列成一种可以同时发生的方式。如果计算机配备了一种特殊的、能够同时将单个信息片段复制到许多其他地方的能力，整个过程就可以压缩成一个常数深度的电路。这意味着随着系统规模的增大，所需的时间完全不会增加。即使没有这种特殊能力，所需的时间也仅呈对数级增长，这与此前认为不可避免的指数级增长相比，增长速度非常缓慢。

这一发现挑战了“复杂量子系统必须演化缓慢”的直觉。在物理学中，存在一种普遍观点，即模拟一个系统的随时间演化需要与所模拟的时间成比例的步骤。研究人员承认，当辅助粒子非常少时，这种直觉是成立的，但他们的工作表明，当允许使用大量的额外空间时，规则就会发生改变。通过将空间作为一种资源，时间演化可以被“快进”。这并不违反物理定律；相反，它揭示了此前被隐藏的、关于时间与空间之间的新型权衡关系。研究人员谨慎地指出，虽然他们的方法证明了这种快进在理论上是可能的，但所需的辅助粒子数量是巨大的，会随系统规模呈指数级增长。这使得该方法目前在大型应用中尚不具备实用性，但它从根本上改变了我们对量子计算可能性的理解。

该论文还探讨了量子复杂度与经典复杂度之间的关系。多年来，人们一直不清楚创建量子规则的难度是否与解决经典问题的难度相关联。研究人员的方法依赖于量子合成与经典技术（用于私密检索信息和局部解码信息）之间的一种深层联系。通过将这些领域联系起来，他们得以借鉴密码学和编码理论中的强大工具来解决量子力学中的问题。这种跨学科的思想碰撞让他们能以全新的视角看待问题，揭示了量子规则的复杂度并非孤立的谜团，而是与信息本身的结构有着深刻的交织关系。

最后，这项工作是一项原理性的证明，证明了通用量子操作所需的指数深度并非根本性的障碍。它表明，只要有足够的资源，任何量子变换都可以被并行化为浅层电路。研究人员通过构建一个特定的算法实现了这一点，该算法使用了一个二次相位算子（quadratic phase oracle）——一种将规则编码进波状相位的数学工具——然后使用一系列傅里叶变换进行解码。他们证明了这个过程在连续设定下可以做到精确，并且可以被离散化以在有限网格上运行且误差微乎其微。整个构建过程是严谨且符合数学逻辑的，为实现常数深度量子电路提供了具体的路径。虽然所需粒子数量之巨意味着这目前还不是构建实用量子计算机的蓝图，但它开启了我们理解量子复杂度的新篇章，表明量子计算的极限比我们曾经认为的要灵活得多。

技术摘要：所有幺正变换均具有常数深度量子电路

1. 问题陈述

本文探讨了一个基本问题：实现任意 $n$ 位量子比特幺正变换 $U \in U(N)$ （其中 $N=2^n$ ）所需的电路深度。虽然已知任何此类幺正变换都可以使用 $2^{O(n)}$ 个单比特和双比特门进行合成，但即便在拥有无限辅助量子比特的情况下，这种指数级的门数量是否必然导致指数级的电路深度，仍然是一个悬而未决的问题。

来自物理学的直觉以及量子复杂性理论通常认为，模拟一般的哈密顿量演化或实现任意幺正变换需要与操作复杂度成正比的时间（深度），这可能意味着无法进行显著的并行化。具体而言，“快速前推定理”（No Fast-Forwarding Theorem）[BACS07] 以及关于最大复杂度增长（例如在纠缠系统如 SYK 模型 [BRS+16, BDKP20] 中）的猜想都表明，一般的幺正变换无法在亚线性或常数时间内执行。本文通过证明在具备充足空间（辅助量子比特）的情况下，可以通过“以空间换时间”来实现多项式甚至常数深度的变换，从而挑战了这一直觉。

2. 方法论

作者的方法将幺正合成问题（Aaronson 和 Kuperberg [AK07]）与局部可解码码（LDCs）及私有信息检索（PIR）的概念联系起来。

2.1. 核心算法：三查询合成

其核心技术贡献是一个连续变量算法，该算法仅需对特定的对角相位算符进行三次查询，即可合成目标幺正变换 $S$ （在不失一般性的情况下，将其简化为无迹实对称对合矩阵）。

该算法作用于 $N$ 模量子谐振子的单激发扇区。步骤如下：

编码： 将输入态 $|\psi\rangle \in \mathbb{C}^N$ 相干地编码到谐振子的单激发子空间中。这通过使用高斯波函数将基态 $|x\rangle$ 映射为类似于“独热”（one-hot）编码的状态。
算符查询： 应用一个对角算符 $Q_S$ ，根据连续空间中的位置向量 $\vec{v}$ 施加相位 $e^{\frac{i}{2}\vec{v}^T S \vec{v}}$ 。该相位是幺正矩阵项的二次型。
傅里叶变换： 应用量子傅里叶变换（QFT）。
重复： 在应用 QFT 后再次应用算符和 QFT，共计两次。
解码： 应用逆编码映射。

作者证明了复合算符 $i E^\dagger Q_S F Q_S F Q_S E$ 能够精确恢复目标幺正变换 $S$ 。其直觉在于，夹在傅里叶变换之间的二次相位算符实际上是在一条线上的三个点探测二次型。这使得可以通过二次多项式解码恒等式来恢复矩阵项 $\langle y|S|x\rangle$ ，类似于 Bernstein-Vazirani 算法恢复线性函数的方式。

2.2. 离散化

为了从连续变量理想化模型过渡到有限量子电路，作者将谐振子状态离散化到网格 $\Lambda^N$ 上。

网格构建： 在每个维度内受限区域内的 $\Theta(\log(N/\epsilon))$ 个点上采样一个规则网格。
误差分析： 利用泊松求和公式（Poisson Summation Formula），界定了对连续波函数进行欠采样以及对无限晶格进行截断所引入的误差。他们证明，误差主要由位置基底和傅里叶基底中高斯分布的尾部决定。
结果： 通过适当选择 $K$ ，离散化算法可以在算符范数误差 $\epsilon$ 内逼近目标幺正变换。

2.3. 浅层实现

最后一步是使用浅层电路实现离散化算法的组成部分：

编码/解码： 通过相干态制备和使用 fan-out 门的“独热”编码来实现。
对角相位算符： 该二次相位被分解为 $N^2$ 个两两相互作用。利用无界 fan-out 门，这些操作可以并行计算。
离散傅里叶变换 (QFT)： 作者利用基于精确相位解码和模运算的常数深度构造来实现网格上的 QFT，并利用 fan-out 门来并行化必要的运算。

3. 核心贡献与结果

3.1. 主要定理

本文确立了关于幺正变换合成电路深度的两个主要结果：

定理 1.1（多项式深度）： 若提供 $2^{O(n)}$ 个辅助量子比特，则每个 $n$ 位幺正变换都可以通过深度为 $\text{poly}(n, \log(1/\epsilon))$ 的单比特和双比特量子电路在误差 $\epsilon$ 内得到近似。
定理 1.1（常数深度）： 如果扩展电路模型以允许使用无界 fan-out 门（规模为 $2^{O(n)}$ ），则深度可以降低至常数（ $O(1)$ ）。

3.2. 查询复杂度

本文提供了第一个相对于算符的常数查询幺正合成算法。

定理 1.2： 存在一个固定的量子查询算法，通过对对角相位算符进行三次查询（或对经典算符进行六次查询），即可实现任何误差为 $\epsilon$ 的幺正变换 $U \in U(N)$ 。
这改进了以往需要 $\sqrt{N}$ 次查询或对 $N^2$ 个比特进行经典查询的界限。

3.3. 技术创新

二次 LDC： 作者将幺正合成与线性局部可解码码（LDCs）之间的民间联系扩展到了二次 LDC。该算法有效地实现了一个 2-服务器 PIR 方案，其中数据库是幺正矩阵，但查询机制使用的是二次相位而非线性相位。
用于离散化的泊松求和法： 使用泊松求和公式来严格界定连续变量算法的离散化误差，是实现从连续到有限近似算法过渡的关键技术工具。

4. 重要性与主张

本文声称其结果在物理学视角下是令人惊讶的，因为它们展示了模拟一般幺正演化所需的“时间”（电路深度）可以与“空间”（辅助量子比特）进行交换。

并行化： 该工作证明了每个幺正变换都可以被并行化为多项式或常数深度，这推翻了“一般幺正变换合成本质上需要深层电路”的直觉。
复杂性理论： 它建立了幺正合成、PIR 与 LDCs 之间的深刻联系，表明幺正变换的复杂度并非与经典复杂性理论脱节，而是可以被归约为具有极低查询复杂度的特定算符问题。
局限性： 作者明确指出，这一结果依赖于指数数量的辅助量子比特（ $2^{O(n)}$ ）。这是一种“以空间换时间”的权衡。该结果并不意味着可以用多项式空间实现常数深度的幺正变换；相反，它表明在拥有指数空间时，可以打破深度壁垒。

文章总结道，虽然“快速前推定理”在算符模型中关于查询次数（query count）的限制依然成立，但当允许足够的资源（辅助比特和 fan-out 门）时，它并不排除将这些查询并行化为常数深度的可能性。