基本门分解｜中性原子量子计算知识库

基本门分解（elementary gates）回答一个看似平凡的问题：任意 n 比特幺正变换能否、以及要用多少个”单比特门 + CNOT”精确实现？答案是肯定的——代价指数级（ $Θ (n^{3} 4^{n})$ ）——而正是这个”通用但昂贵”的标准构造，划定了编译器必须去优化的起点。

问题背景

量子算法通常以逻辑级描述（QFT、Grover 算符、受控旋转等任意幺正），而硬件只执行固定的原生门集。Barenco 等人 1995 年的经典工作给出了第一个系统性答案：由全部单比特门（ $U (2)$ ）与异或门（CNOT）构成的门集是通用的——任意 $n$ 比特幺正 $U (2^{n})$ 都能表示为它们的有限复合 Barenco 1995。同一时期 Deutsch、Lloyd 与 Sloane 也独立证明了此类通用性。此后 Vatan–Williams、Möttönen 等与 Shende–Bullock–Markov 把分解的门数不断压低并证明最优性 Vatan 2004 Möttönen 2004 Shende 2006。

这一构造有两重意义。其一是理论底线：它证明了门集通用，并给出渐近复杂度的上界与下界；其二是工程起点：现代编译器（如 Qiskit 的 unitary synthesis）内置了这类分解，作为优化的输入——后续一切化简（见T 计数约简与ZX 演算）都在其上进行。

理论模型

通用性与两比特门

通用性证明的核心是”先对角化、再逐项实现”。任意 $U \in U (2^{n})$ 可写为对角相位矩阵 $D$ 与一系列双态旋转 $T (x_{1}, x_{2})$ （仅在基矢 $∣ x_{1} ⟩, ∣ x_{2} ⟩$ 张成的二维子空间内旋转）之积；每个 $T (x_{1}, x_{2})$ 用 Gray 码把 $x_{1}$ 逐位”搬”到 $x_{2}$ ，配合多控门实现 Barenco 1995。计数结果：

任意 U (2^{n}) 精确实现需要 Θ (n^{3} 4^{n}) 个基本门（无 ancilla ） ，

与维数计数下界 $Ω (4^{n})$ （ $U (2^{n})$ 有 $4^{n}$ 个自由参数，每个两比特门至多提供 15 个）只差多项式因子——“几乎所有”幺正都注定指数昂贵。

两比特情形已被彻底解决：任意两比特幺正按 Cartan（KAK）分解可写成

U = (A_{1} \otimes A_{2}) e^{- i (c_{1} X \otimes X + c_{2} Y \otimes Y + c_{3} Z \otimes Z)} (B_{1} \otimes B_{2}),

Vatan–Williams 由此给出显式构造：至多 3 个 CNOT 与 15 个单比特门；若幺正是纯实的，则至多 2 个 CNOT 与 12 个单比特门，并在 {CNOT, $y$ -旋转, $z$ -旋转, phase} 门族内证明了最优性 Vatan 2004。

多比特分解与受控门

对一般 $n$ 比特门，Möttönen 等给出基于余弦-正弦分解（cosine-sine decomposition, CSD）的构造：将矩阵按前后半空间分块 $U = (A C B D)$ ，递归地用受控旋转实现。该构造的单比特门数 $4^{n}$ 达到维数下界，CNOT 数从先前分解的 $4^{n} - 2^{n} + 1$ 改进为 $4^{n} - 2^{n + 1}$ Möttönen 2004；已知的 CNOT 计数下界为 $⌈ \frac{1}{4} (4^{n} - 3 n - 1)⌉$ 。Shende–Bullock–Markov 则用布尔函数 Shannon 分解的类比与”量子多路复用器”（quantum multiplexor）模块给出渐近最优的分解与寄存器初始化线路，与下界至多相差因子 2 Shende 2006。

受控门是构造的胶水。Barenco 等证明：

一般 $\land^{2} (U)$ （三比特受控门）至多用 16 个基本门（8 单比特 + 8 CNOT）模拟；允许整体相位时更省 Barenco 1995；
特别的 Toffoli 门 $\land^{2} (σ_{x})$ 只需恰好 5 个两比特门（推广 Sleator–Weinfurter 方案）；
$n$ 比特 Toffoli $\land^{n - 1} (σ_{x})$ 可用 $8 (n - 5)$ 个三比特 Toffoli 与 $48 n - 204$ 个基本门模拟（需 1 个工作比特），或在工作比特受限时用二次规模的递归构造；非平凡 $\land^{n - 1} (U)$ 有 $Ω (n)$ 下界 Barenco 1995。

CSD 分块递归结构与受控旋转电路（图源：Möttönen 2004 Fig. 1）

寄存器初始化与量子多路复用器

Shende–Bullock–Markov 指出，除了通用计算，寄存器初始化（把任意基矢制备为给定叠加态）本身是个非平凡任务，因为 $n$ 比特态空间含指数多的叠加分量。他们提出的”量子多路复用器”（quantum multiplexor）模块统一了若干已知构造：以布尔函数 Shannon 分解的类比逐位分叉，配合受控旋转实现任意态制备与通用幺正；两类任务都是渐近最优的，且把此前已知的 CNOT 计数至少改进一倍 Shende 2006。对含大量态制备步骤的算法（变分线路初态、振幅编码），这条独立于通用分解的路径往往更省。

方法与实现

标准分解已内置于主流工具链：任意幺正矩阵输入后先做 KAK/CSD 分解，再化简单比特门串。使用时有三条经验：

别把通用分解当终点。通用 $n$ 比特分解指数贵，实际电路几乎总含可利用结构——对角结构交给对角线路综合，Pauli 旋转串交给相位 Gadget，Clifford+T 交给T 计数约简与超优化。
连通性约束代价可观。Shende 等分析指出，在最邻近耦合架构上做分解会使门数增加近一个数量级，但保持渐近最优 Shende 2006；中性原子阵列可通过原子搬运（见布局映射与长程交互利用）回避这一惩罚。
原生多比特门应被利用而非分解掉。受控门构造（5 门 Toffoli、 $\land^{n - 1} (U)$ 的二次构造）在中性原子上是多余的：里德堡阻塞天然提供多比特受控相位（见多比特阻塞门与Toffoli/CCZ 门）。Geyser 框架据此把两比特门对合并回原生 CCZ Staudacher 2024；多控相位门综合更进一步的动机正是”标准分解绕开了硬件最便宜的门”。

编译器评测的公平性也要求把分解质量与后续优化分开记账：同一通用分解接不同化简流水线（PyZX、t|ket⟩、Quartz）的结果可能相差数倍，方法见编译器公平评测与可视化。

连续参数门（任意单比特旋转）还需离散化到有限门集，这由Solovay-Kitaev 定理与算法及其后继承担。

参数与量级

量	数值	来源
通用门集	全部单比特门 + CNOT，可精确实现任意 $U (2^{n})$	Barenco 1995
通用 $n$ 比特幺正	$Θ (n^{3} 4^{n})$ 个基本门（无 ancilla）	Barenco 1995
任意两比特门	$\leq 3$ CNOT + 15 单比特门（最优）	Vatan 2004
纯实两比特幺正	$\leq 2$ CNOT + 12 单比特门（最优）	Vatan 2004
$n$ 比特 CNOT 计数	上界 $4^{n} - 2^{n + 1}$ ；下界 $⌈ \frac{1}{4} (4^{n} - 3 n - 1)⌉$	Möttönen 2004
Toffoli 门	恰好 5 个两比特门	Barenco 1995
$n$ 比特 Toffoli	$8 (n - 5)$ 个 Toffoli + $48 n - 204$ 基本门（1 工作比特）	Barenco 1995
渐近最优性与连通性	与 CNOT 下界差至多因子 2；最邻近约束门数增近一个数量级	Shende 2006

与其他概念的关系

Solovay-Kitaev 定理与算法：基本门分解允许连续单比特门，若门集离散（如 Clifford+T），需要 SK 类算法以 polylog 代价逼近。
对角线路综合与相位 Gadget：通用分解指数昂贵，结构化幺正（对角 / Pauli 旋转串）有专属的多项式构造，是实践中更常用的”分解”。
Toffoli/CCZ 门与多比特阻塞门：Barenco 构造中代价最高的受控门，恰是里德堡平台的原生资源。
Geyser：原生多比特门编译：把标准两比特门分解”逆向”合并回原生 CCZ 的编译框架。
多控相位门综合：面向中性原子原生 CnP 门的精确综合，规避通用分解。
受限寻址的分解与调度：同样的”分解 + 调度”问题在里德堡寻址约束下的对应版本。
电路等价性验证：分解后的电路须与原幺正等价，验证同样基于 ZX 等图形演算。
Quartz 超优化：在基本门级电路上做等价替换搜索，进一步压低门数。

参考文献

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, et al., “Elementary gates for quantum computation”, Phys. Rev. A 52, 3457 (1995). NA088 · DOI 10.1103/PhysRevA.52.3457 · arXiv:quant-ph/9503016
F. Vatan, C. Williams, “Optimal quantum circuits for general two-qubit gates”, Phys. Rev. A 69, 032315 (2004). NA089 · DOI 10.1103/PhysRevA.69.032315
M. Möttönen, J. J. Vartiainen, V. Bergholm, M. M. Salomaa, “Quantum Circuits for General Multiqubit Gates”, Phys. Rev. Lett. 93, 130502 (2004). NA090 · DOI 10.1103/PhysRevLett.93.130502
V. V. Shende, S. S. Bullock, I. L. Markov, “Synthesis of quantum-logic circuits”, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (2006). NA091 · DOI 10.1109/TCAD.2005.855930

中性原子百科

探索

基本门分解