T 计数与非 Clifford 约简｜中性原子量子计算知识库

在 Clifford+T 容错模型里，一个 T 门比 Clifford 门贵数百倍（魔态蒸馏），T-count 因此成为编译质量的硬指标；ZX 演算的"相位传送"（phase teleportation）让非 Clifford 相位沿线路非局域地传播、配对相消——不改变 Clifford 门的数目与位置，就能再省 20-50% 的 T 门。

问题背景

容错量子计算的标准模型把电路编译到 Clifford+ $T$ 门集：Clifford 门（H、S、CNOT）在多数纠错码上可低成本横向/冒充实现，而 $T = diag (1, e^{iπ /4})$ 非克利福德，须由魔态蒸馏（magic state distillation）制备——每个 T 门的时空开销比 Clifford 门大数百倍 Heyfron 2018。于是 T-count（电路中 T 门总数）与 T-depth（沿关键路径的 T 层数）直接决定逻辑时钟数与蒸馏工厂规模。

单比特 Clifford+ $T$ 的最优综合已基本解决；多比特情形的最优编译经典运行时间随比特数指数增长 Heyfron 2018。实践路线是多项式时间的启发式化简：Todd 编译器（Hadamard 分块 + 奇偶网络再综合）Heyfron 2018、PyZX 的 ZX 化简与相位传送 Kissinger 2020、以及 CNOT-phase 电路的奇偶网络启发式 Amy 2018。

理论模型

相位多项式与奇偶网络

CNOT 与 $Z$ 基旋转（ $R_{Z} (θ)$ ）构成的电路作用于基矢时，每条线的值始终是输入比特的线性函数（奇偶）。Amy–Azimzadeh–Mosca 建立的线路-多项式对应：此类电路的幺正由伪布尔函数的 Fourier 展开

f (x) = y \in F_{2}^{n} \sum b_{f} (y) (- 1)^{y \cdot x}

唯一刻画，Fourier 支撑集（非零系数的奇偶项集合）决定实现它所需的奇偶网络，也为 T-count 提供了不可约的参照 Amy 2018。这一对应是对角线路综合中相位多项式的一般化，把”电路代价”翻译成”函数复杂度”。

相位传送示意：非 Clifford 相位沿 ZX 图非局域传播并配对相消（图源：Kissinger 2020 Fig. 1）

Todd：Hadamard 分块与奇偶网络再综合

Heyfron–Campbell 的 Todd 编译器把 Clifford+ $T$ 电路改写为 ” $⟨ CNOT, T ⟩$ 与 $⟨ H ⟩$ 子电路交替”的分块结构。处理 Hadamard 有两条路线：其一，Hadamard 有界分块——按 Hadamard 位置切分并逐块独立优化；其二，用测量-制备 gadget 替换每个 Hadamard，把修正集中成后置电路 $E_{p os t}$ ，避免了逐块独立优化造成的次优。每个 CNOT+T 块的功能是奇偶函数集合，T-count 等于所需奇偶的规模；对奇偶集合做拟阵划分（matroid partition）并再综合，即可压低 T-count。随机电路基准显示 T-count 随比特数按 $O (n^{2})$ 标度，Todd 在所有变体中平均最低，且在基准中往往取得比同框架 TOOL 编译器更低的 T-count Heyfron 2018。

下界与复杂度：为什么只能启发式

Amy–Azimzadeh–Mosca 的结果同时说明了化简的天花板：对某些函数类，Fourier 展开唯一决定最小 CNOT 代价；而”计算给定奇偶集合的奇偶网络”这一核心子问题，在所有 CNOT 同靶、以及输入编码于更大空间（正是 Clifford+ $T$ 电路 CNOT 优化的归约来源）两个受限情形下均为 NP 完全 Amy 2018。这为实践定了调：大规模 Clifford+ $T$ 电路的 T-count/CNOT 最小化只能依赖多项式启发式（Todd、PyZX、奇偶网络启发式），配合超优化在小规模块上逼近精确最优。

相位传送：ZX 视角

Kissinger–van de Wetering 把电路变成 graph-like ZX 图：非 Clifford 相位挂在蜘蛛上，经局部补元（local complementation）与 Pauli 对消等规则化简后，“内部态”中的相位可以非局域地传送——让两个 T 相位沿图传播到同一蜘蛛上直接相消，甚至移出边界（“phase teleportation”）。该方法的两个特点 Kissinger 2020：

不改变非相位门的数目与位置，也适用于任意非 Clifford 相位门与含未知参数的参数化电路；
同一套化简策略足以验证化简前后电路等价（见电路等价性验证），已在 36 个 Clifford+ $T$ 基准上闭环确认正确性。

方法与实现

实践中三层流水线：

初编译：基本门分解或专用分解得到 Clifford+ $T$ 电路；
T-count 化简：PyZX full_reduce + 相位传送（开源实现于 PyZX），或 Todd（C++ 实现）；两者可级联；
CNOT 化简：对产物做奇偶网络启发式再综合，平均再省 CNOT Amy 2018；
正确性闭环：PyZX 的化简策略同时能验证电路相等——NA106 对全部基准组合了化简前后电路并验证等价 Kissinger 2020。

基准数字：

Todd：对可逆逻辑基准库中 97% 的电路降低 T-count，相对此前最优分解平均省 20%，最好一例 51% Heyfron 2018；
PyZX：无 ancilla 情形下对多数基准持平或超过此前方法、最好提升达 50%；36 个 Clifford+ $T$ 基准（与前人工作共用）中 26 个（约 72%）达到或刷新最优、6 个（约 17%）刷新纪录 Kissinger 2020；
奇偶网络启发式：在 Clifford+ $T$ 基准上平均削减 CNOT 23%、最多 43% Amy 2018。

与中性原子平台的关联

中性原子把”哪个门最贵”整个改写：连续角度的里德堡受控相位一次脉冲完成（阻塞 CZ 门、奇偶相位门与原生多体门），T-count 类离散指标在物理层不再适用；NA 平台的对应成本是全球里德堡脉冲数与脉冲时间，这正是多控相位门综合以 $C^{n} P$ 取代 CNOT 分解的出发点。但 T-count 理论并未退役：其一，逻辑量子处理器与qLDPC 码架构等容错方案在逻辑层仍是 Clifford+ $T$ （或类似离散）门集，逻辑编译流水线中的 T-count/T-depth 优化直接决定蒸馏工厂规模（见常数开销容错）；其二，相位多项式/奇偶网络方法与中性原子原生门共享数学内核——对角相位合成（对角线路综合）。

参数与量级

量	数值	来源
T 门相对成本	比 Clifford 门贵数百倍（魔态蒸馏）	Heyfron 2018
随机电路 T-count 标度	$O (n^{2})$	Heyfron 2018
Todd：受益电路比例	97%（相对此前最优分解）	Heyfron 2018
Todd：平均 T-count 节省	20%，最好 51%	Heyfron 2018
Todd：编译器对比	常低于同框架 TOOL 的 T-count	Heyfron 2018
PyZX：相对 SOTA 提升	至多 50%；72% 基准持平或更优，17% 刷新纪录	Kissinger 2020
PyZX：基准规模	36 个 Clifford+ $T$ 基准（正确性经 ZX 验证）	Kissinger 2020
奇偶网络启发式 CNOT 节省	平均 23%，最多 43%	Amy 2018
复杂度结论	CNOT 最小化两个受限情形 NP 完全	Amy 2018

与其他概念的关系

基本门分解：T-count 优化的输入来源；通用分解产物通常远非 T-最优。
ZX 演算与PyZX 与图论化简：相位传送的数学框架与开源实现；图重写规则与 T-count 约简共用。
对角线路综合与相位 Gadget 与浅深综合：共享相位多项式/奇偶网络数学内核的结构化综合。
电路等价性验证：ZX 化简在压低 T-count 的同时自动给出等价性证明。
Quartz 超优化：等价替换搜索可作为 T-count 流水线之后的补充优化层。
逻辑量子处理器与qLDPC 码架构：决定逻辑层门集与蒸馏开销，T-count 在此层兑现为时空成本。
编译器公平评测与可视化：T-count 优化器之间公平对比的方法学参照。
通用量子基准套件：T-count 优化效果的基准电路来源。

参考文献

L. E. Heyfron, E. T. Campbell, “An efficient quantum compiler that reduces T count”, Quantum Sci. Technol. (2018). NA096 · DOI 10.1088/2058-9565/aad604 · arXiv:1712.01557
A. Kissinger, J. van de Wetering, “Reducing the number of non-Clifford gates in quantum circuits”, Phys. Rev. A 102, 022406 (2020). NA106 · DOI 10.1103/PhysRevA.102.022406
M. Amy, P. Azimzadeh, M. Mosca, “On the controlled-NOT complexity of controlled-NOT-phase circuits”, Quantum Sci. Technol. (2018). NA098 · DOI 10.1088/2058-9565/aad8ca

中性原子百科

探索

T 计数与非 Clifford 约简