基本门分解

基本门分解研究如何把任意量子门表示（通常是近似表示）为由少数原生门组成的线路。物理器件只稳定支持很小的门库（如超导平台的 ${R_{z}, X, X}$ + CNOT，离子阱的任意单比特旋转 + $Z Z (θ)$ ），而算法层面写下的门五花八门，中间必须靠分解理论衔接。它与多控门分解一起，构成量子算术电路及几乎所有实用线路的编译基础。

本词条给出四个层面的完整理论：单比特门（Euler 角分解）、离散万能门集（稠密性与 Solovay–Kitaev 定理）、两比特门（KAK 分解与 3-CNOT 定理）、三比特门（Toffoli 分解）。

历史脉络

万能性的确立（1989–1995）：Deutsch（1989）证明三比特通用门存在；DiVincenzo（1995）与 Barenco 等（1995）把万能门集缩到”任意单比特门 + 一个两比特纠缠门”，Barenco 等的论文同时给出多控门与 Toffoli 分解的系统构造，是整个领域的奠基文献。
离散门集的万能性：Boykin 等（1999）严格证明 ${H, T, CNOT}$ 万能—— $⟨ H, T ⟩$ 在 $S U (2)$ 中稠密；Solovay（1995，未发表）与 Kitaev（1997）独立给出的 Solovay–Kitaev 定理保证逼近只需 $O (lo g^{c} (1/ ε))$ 个门，Dawson–Nielsen（2006）给出标准算法实现。
精确与最优综合（2012–2014）：Kliuchnikov–Maslov–Mosca 证明大量单比特门可被 Clifford+ $T$ 精确综合；Ross–Selinger 用数论格基归约给出 $O (lo g (1/ ε))$ 的最优序列综合——把 SK 的多项式对数降到对数。
$T$ 经济学：容错语境下 $T$ 门依赖魔术态蒸馏， $T$ 数量（T-count）与 $T$ 深度（T-depth）取代门数成为首要优化目标，Gidney 的临时逻辑与等技巧把算术线路的 $T$ 开销持续压低。

单比特门：Euler 角分解

命题：不计全局相位，任意 $U \in S U (2)$ 可写成

$U = R_{z} (β) R_{y} (γ) R_{z} (δ), R_{σ} (θ) = e^{- i θ σ /2} .$

构造性证明：直接把矩阵元对齐。设

$U = (a - b^{*} b a^{*}), ∣ a ∣^{2} + ∣ b ∣^{2} = 1,$

（ $S U (2)$ 的一般形式）。而

$R_{z} (β) R_{y} (γ) R_{z} (δ) = (e^{- i (β + δ) /2} cos \frac{γ}{2} e^{i (β - δ) /2} sin \frac{γ}{2} - e^{- i (β - δ) /2} sin \frac{γ}{2} e^{i (β + δ) /2} cos \frac{γ}{2}) .$

比较左上角元素： $∣ a ∣ = cos (γ /2)$ 定出 $γ \in [0, π]$ ；辐角 $ar g a = - (β + δ) /2$ ；再比较 $b$ 的辐角定出 $(β - δ) /2$ 。两个辐角方程恰好解出 $β, δ$ ，三个实参数 $β, γ, δ$ 与 $S U (2)$ 去掉全局相位后的三个自由度一一对应。 $■$

ZYZ 之外还有 ZXZ、XYX 等变体，按硬件原生旋转轴选择。任意单比特门 = 两个 $R_{z}$ 夹一个非对角旋转；在超导等平台上 $R_{z}$ 是”虚拟门”（参考系更新，零成本、零时长），实际开销集中在非对角旋转上——用 $R_{x} (θ) = H R_{z} (θ) H$ 把 $x$ 轴旋转转到位， $R_{y}$ 再经 $R_{z}$ 共轭即可（ $R_{y} (θ) = R_{z} (\frac{π}{2}) R_{x} (θ) R_{z} (- \frac{π}{2})$ ）。

万能门集与稠密性

命题： ${H, T, CNOT}$ 是万能的——对任意 $n$ 比特幺正 $U$ 与精度 $ε > 0$ ，存在该门集上的线路 $V$ 使 $∥ V - U ∥ \leq ε$ 。

论证分两半：

单比特稠密性： $T$ 是绕 $z$ 轴的 $π /4$ 型旋转，而 $H T H$ 给出绕 $x$ 轴的 $π /4$ 型旋转——两条旋转轴恰好垂直（ $z ⊥ x$ ）。稠密性不来自单个门，而来自复合：形如 $T^{- 1} (H T H)$ 的复合门是绕某条轴的旋转，按 $e^{iλπ \overset{n}{^} \cdot σ}$ 记法其角参数满足 $cos (λπ) = cos^{2} (π /8)$ ，对应无理的 $λ$ ——旋转角是无理数倍 $π$ ，群轨道无法封闭成有限点集；Boykin 等沿此完成 $⟨ H, T ⟩ \subseteq S U (2)$ 稠密的严格证明。于是任意单比特旋转可被任意精度逼近。
两比特纠缠 + 全体单比特 = 万能：Barenco 等证明任一两比特纠缠门（如 CNOT）配合任意单比特门可实现任意 $n$ 比特幺正。纯单比特门永远制造不出纠缠，这一步不可省。 $■$

一个实用的推论：由于 $R_{z} (θ)$ 可被 ${H, T}$ 逼近（ $T$ 即 $R_{z} (π /4)$ ， $H T H$ 即 $R_{x} (π /4)$ ，两者组合生成稠密集），编译流程的最后一步总是”单比特旋转 → Clifford+ $T$ 序列”。

Solovay–Kitaev 定理

定理（Solovay 1995; Kitaev 1997）：设 $G$ 是 $S U (d)$ 中稠密、逆封闭的有限门集，则存在常数 $c$ ，使任意 $U$ 可被长度 $O (lo g^{c} (1/ ε))$ 的 $G$ -序列逼近到 $ε$ 。Dawson–Nielsen 的标准递归实现给出 $c \approx 3.97$ 。

递归构造骨架（证明思路）：核心是群交换子恒等式

$U_{gc} (V, W) = V W V^{†} W^{†},$

引理：距单位元 $O (ε)$ 的邻域内，任何残差都可精确写成平衡群交换子 $V W V^{†} W^{†}$ （ $V, W$ 仍在该邻域内）；再用 $ε$ 级子序列替换 $V, W$ ，替换误差在交换子结构下相消，整体误差压到 $O (ε^{3/2})$ 。Dawson–Nielsen 的实现：每层用一个平衡群交换子配一条净近似基准序列； $V, W$ 各用一条 $ε^{2/3}$ 级子序列， $V^{†}, W^{†}$ 由 $V, W$ 的子序列逆序复用，每层共 5 条子序列，层间误差关系 $ε_{k} = c_{0} ε_{k - 1}^{3/2}$ ；门数每层乘 5、精度开 $3/2$ 次方，得 $c = lo g 5/ lo g (3/2) \approx 3.97$ 。更早的 Kitaev–Shen–Vyalyi（2002）已给出任意大于 3 的指数，Kuperberg（2023）在一般逆封闭门集上进一步压到约 $lo g_{φ} 2 \approx 1.44 + δ$ （ $φ$ 为黄金比）。 $■$

门数对精度只是”对数的多项式”级依赖——这是量子计算可行性论证的重要一环：离散门集的物理可执行性不付出多项式代价。实践中现代编译器用数论精确综合（Kliuchnikov–Maslov–Mosca：单比特门可被 Clifford+ $T$ 精确表示当且仅当其矩阵元属于环 $Z [i, 1/ 2]$ ；Ross–Selinger 的格归约算法给出 $O (lo g (1/ ε))$ 长度、实测近乎最优的序列），常能给出比通用 Solovay–Kitaev 短得多的 Clifford+ $T$ 序列。优化目标集中在 T-count 上： $T$ 门在容错实现中依赖魔术态蒸馏，是昂贵的非 Clifford 资源。

两比特门：KAK 分解与 3-CNOT 定理

任意两比特幺正 $U \in S U (4)$ 的结构由 Cartan（KAK）分解给出：

$U = (K_{1} \otimes K_{2}) e^{i (a X \otimes X + b Y \otimes Y + c Z \otimes Z)} (K_{3} \otimes K_{4}),$

其中 $K_{i}$ 是单比特幺正，交互项由三个实参数 $(a, b, c)$ 刻画（模掉局部等价类后两比特门恰有 3 个自由度）。 $(a, b, c) = 0$ 的门是局部门（无纠缠）；仅 $c = 0$ 并不足以判定局域——CNOT 的正则坐标是 $(π /4, 0, 0)$ ，仍是纠缠门。

3-CNOT 定理（Vatan–Williams）：任意两比特幺正都可分解为至多 3 个 CNOT 与 15 个单比特门；且 3 个 CNOT 是紧的——随机两比特门几乎都需要 3 个（SWAP 的正则坐标 $(π /4, π /4, π /4)$ 本身就取满 3 个）。构造思路：先用 KAK 分解化到正则形 $e^{i (a X X + bY Y + c Z Z)}$ ，再按 Vatan–Williams 模板用 3 个 CNOT 与中间单比特旋转交错实现正则门（纯实幺正的特殊子类可省到 2 个 CNOT + 12 个单比特门）。

由此得到标准的逐层编译流程：

$任意线路 \to {CNOT} + {单比特门} \to {CNOT} + {R_{z}, R_{y}} \to {CNOT} + {H, T} (近似) .$

两个常用恒等式：

$SWAP = 3$ 个 CNOT（两两交替交换： $CNOT_{12} CNOT_{21} CNOT_{12}$ ，直接验证三比特基矢上的作用即可）；
$CNOT = (I \otimes H) CZ (I \otimes H)$ ：控制-非与控制-Z 由目标侧 Hadamard 互化，硬件实现其一即可。

精确最优的下界直觉：CNOT 是非局域门，计数下界由纠缠产生能力刻画（1 个 CNOT 至多增加 1 ebit），所以”3 个 CNOT 足够、一般不可再省”与两比特态的最大纠缠度相容。

Toffoli 门分解

Toffoli 门（受控-受控-非，见多控门分解）是量子算术的主力门，不属于 Clifford 群，必须进一步分解：

两比特门版：Barenco 等（1995）的标准构造用 5 个两比特门（V 门技巧在 Toffoli 上的特化，见多控门分解的完整推导）；若只允许 CNOT 与单比特门，则需 6 个 CNOT，Shende–Markov（2009）证明 6 是最优的。
Clifford+ $T$ 版：不用辅助比特时 Toffoli 的最优构造用 7 个 $T$ 门（加 Clifford 门），且 7 是匹配下界——Gosset–Kliuchnikov–Mosca–Russo 证明无辅助比特的 Toffoli/Fredkin 任何 Clifford+ $T$ 实现都至少需要 7 个 $T$ 。借助辅助比特与测量反馈（Gidney 的临时逻辑与：制备 4 个 $T$ 、测量擦除 0 个，净 4 个 $T$ /次；因一个 AND 可替代一对 Toffoli，折算每个被替代的 Toffoli 约 2 个 $T$ ，见多控门分解）——代价是把纯线路变成带测量的动态线路。

这些常数因子经过算术线路里成百上千个 Toffoli 放大后，直接决定整个算法的物理成本估计。

与硬件门集的对接

不同平台原生门不同：超导 ${R_{z}, X, X} + CNOT / CZ$ ；离子阱任意单比特旋转 + $Z Z (θ)$ （MS 门家族）；编译器（transpiler）负责把上述通用分解再映射到具体原生集并优化门数/深度（重写规则、线路合成、布局布线）。词条层面只需记住两点：万能门集保证”一定能编译”；Euler 分解、3-CNOT 定理与 Solovay–Kitaev 定理刻画”编译得多好”——前两者是精确的，后者给出离散化的渐进代价。

关联词条

下游：多控门分解、量子算术电路、通用量子门集
容错：魔术态蒸馏、容错逻辑门实现

参考文献

D. Deutsch. Quantum Computational Networks. Proc. R. Soc. Lond. A 425, 73 (1989).
D. P. DiVincenzo. Two-Bit Gates Are Universal for Quantum Computation. Phys. Rev. A 51, 1015 (1995). arXiv:cond-mat/9407022
A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter. Elementary Gates for Quantum Computation. Phys. Rev. A 52, 3457 (1995). arXiv:quant-ph/9503016
P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, F. Vatan. On Universal and Fault-Tolerant Quantum Computing. Proc. 40th IEEE FOCS, 486 (1999). arXiv:quant-ph/9906054 —— ${H, T, CNOT}$ 稠密性的严格证明。
C. M. Dawson, M. A. Nielsen. The Solovay-Kitaev Algorithm. Quant. Inf. Comput. 6, 81 (2006). arXiv:quant-ph/0505030
A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi. Classical and Quantum Computation. AMS Graduate Studies in Mathematics 47 (2002). —— SK 指数的改进（任意 $c > 3$ ）。
G. Kuperberg. Breaking the Cubic Barrier in the Solovay-Kitaev Algorithm. (2023). arXiv:2306.13158
F. Vatan, C. P. Williams. Optimal Quantum Circuits for General Two-Qubit Gates. Phys. Rev. A 69, 032315 (2004). arXiv:quant-ph/0308006
V. Kliuchnikov, D. Maslov, M. Mosca. Fast and Efficient Exact Synthesis of Single-Qubit Unitaries Generated by Clifford and T Gates. Quantum Inf. Comput. 13, 607 (2013). arXiv:1206.5236
D. Gosset, V. Kliuchnikov, M. Mosca, V. Russo. An Algorithm for the T-Count. Quantum Inf. Comput. 14, 1261 (2014). arXiv:1308.4134 —— Toffoli 7T 下界。
N. J. Ross, P. Selinger. Optimal Ancilla-Free Clifford+T Approximation of Z-Rotations. Quantum Inf. Comput. 16, 901 (2016). arXiv:1403.2975
V. V. Shende, I. L. Markov. On the CNOT-Cost of TOFFOLI Gates. Quant. Inf. Comput. 9, 461 (2009). —— 6 CNOT 最优性。
C. Gidney. Halving the Cost of Quantum Addition. Quantum 2, 74 (2018). arXiv:1709.06648
Nielsen & Chuang.《量子计算与量子信息》第 4 章（尤其 §4.3 受控运算、§4.5 万能量子门与 Solovay–Kitaev）.

description	把抽象的量子门编译成硬件可执行的少数原生门：单比特 Euler 分解、H/T/CNOT 万能门集与 Solovay–Kitaev 定理、两比特门的 3-CNOT 分解与 Toffoli 门分解。
tags	量子算术
aliases	gate decomposition, Euler 分解, 万能门集, Solovay–Kitaev 定理

量子计算百科

探索