PyZX 与图论化简

PyZX 把 ZX 演算的重写规则编译成图上的批量化简器：单调递减的"蜘蛛数"指标保证终止，局域补图与支点变换负责全局压缩，一条 15 比特 2500 门的 Clifford 电路在笔记本上数秒内被压到正规型——图形化推理由此从纸面演算变成编译器级的基础设施。

问题背景

ZX 演算在纸面上威力巨大，但要服务真实的编译流，必须回答三个工程问题 Kissinger 2020：

1. 规模：优化对象是数百 qubit、上万门的电路，化简器能否在秒级处理数十万顶点的图？
2. 自动化：不能依赖人挑选规则——策略必须”何时停、如何选规则”全部自动；
3. 可信：重写实现是否有误？化简结果与原电路是否确实幺正等价？

PyZX（读作 “physics” 去掉 H）是 GPLv3 开源 Python 库，给出的答案是：把每条规则写成图上匹配-重写循环，用顶点数下降作单调性指标；用基于图论操作（局域补图/支点变换）的复合策略做化简；用张量比对与”化简到恒等”两种办法验证等价 Kissinger 2020。它是目前 ZX 路线线路优化（T 计数与非 Clifford 约简）、等价检查（电路等价性验证）与学习类优化器（ZX 图的深度强化学习优化、Quarl：学习型线路优化器）的共同底座。

理论模型

从重写规则到化简器

PyZX 的化简器（simplifier）= “匹配全部规则应用点 → 重写 → 重复，直到无新匹配”的循环。由于一次匹配不重叠、且重写可能暴露新的匹配点，循环天然需要多轮；为保证终止，每条基本化简器必须单调降低某个图上度量——最常用的是顶点数，也可以是交换顶点类型等更复杂的量 Kissinger 2020。典型原子化简器包括：

• id_simp：删去所有相位为零的二腿蜘蛛（恒等消去）；
• spider_simp：融合同色相邻蜘蛛，相位相加；
• 基于局域补图（local complementation）与支点变换（pivoting）的 lc_simp/pivot_simp：图论级的全局重连。

原子化简器按特定次序循环组合成复合策略。PyZX 的两个顶层策略 Kissinger 2020：

$$\text{clifford\_simp}:\text{Clifford 电路}\to \text{GS-LC 伪正规型},\text{full\_reduce}:\text{Clifford+T 电路}\to \text{相位 gadget 化简}.$$

前者把纯 Clifford 电路压成”图态 + 局域 Clifford”正规型（门数 $2n^2+O(n)$，见ZX 演算）；后者在非 Clifford 情形下把 T 门吸收进相位 gadget，用支点变换”隔空”合并非 Clifford 结构，是无 ancilla T-count 优化的主力 Kissinger 2020。teleport_reduce 则走”相位传送”路线：化简后不经过线路提取，直接在类电路结构间移动相位，从而绕开提取难题。

正确性验证

PyZX 提供两层验证 Kissinger 2020：

• 张量比对：to_tensor() 把图变成 NumPy 张量，compare_tensors 在允许全局非零标量意义下逐元素比较。内存随 qubit 数指数增长，32 位 Python 实际可验证到 10 qubit；
• 化简验证：构造 $c=c_1^{†}\circ c_2$，用 full_reduce 化简；若归约到恒等则等价成立（秒级，可给出重写序列作为证书）；若失败则结论悬而不决——该方法可靠但不完备，性质与电路等价性验证中的系统研究一致。

作者用后者复验了一批已发表电路的”优化前后”对，除一处外全部通过——而那个例外经查确系已发表优化电路本身的错误，这也是图形化简作为编译正确性防线的有力例证 Kissinger 2020。作者据此提出一个可检验的猜想：凡能由基本重写规则互推的两个图，full_reduce 都应能验证其等价——即化简策略的威力上限接近演算本身的推导能力；该猜想随后在带 ancilla 化简、更强策略等方向被持续检验 Kissinger 2020。

化简策略的改进空间：启发式支点

标准策略对支点变换的选择是”贪心降顶点数”，未必对双比特门友好。Staudacher 等把启发式引入化简序列（greedy/随机选支点、配合邻居解融合 neighbour unfusion），在保持 T-count 收益的同时专攻 2Q 门数 Staudacher 2023：启发式方案平均降低 2Q 门约 $19\%$（总门数约 $27\%$），而标准 Clifford 化简平均增加约 $22\%$；相对现有 ZX 方案最高削减 2Q 门 $40\%$；对非 ZX 的最优法（Nam et al.）输出再加工，可在 Adder8 上再降总门数 $15\%$ 以上。

四个候选策略的对比给出了明确的工程结论：贪心、随机、贪心+邻居解融合、随机+邻居解融合中，含邻居解融合的两版在超过 $70\%$ 的电路上取得族内最佳；与 Nam et al. 非 ZX 优化串联（以其输出为输入）后，电路越大改进越显著，“Nam+启发式”组合把平均削减推到总门数约 $29\%$、2Q 门约 $21\%$ Staudacher 2023。

PyZX full_reduce 化简 tof_4 电路前后的 ZX 图对比：上半为原电路图，下半为化简后含 Hadamard 边的图状图（图源：Kissinger 2020 Fig. 1）

方法与实现

• 图数据结构：默认 GraphS 用”字典套字典”存邻接（顶点→邻居→边类型），相位单独存表；这一朴素实现足以在合理时间内处理数十万顶点的化简 Kissinger 2020。图后端可以子类化替换，全部化简器随即复用。
• 缩放行为：Clifford 正规型化简的耗时在固定比特数下呈幂律（幂指数随比特数变化），15 qubit/2500 门 < 5 s 的实测点在一台消费级笔记本上取得；对比之下，通用重写系统 Quantomatic 优化 5 qubit 不足百门的电路需半小时以上——专用数据结构与”每条规则一段手写代码”（不依赖 bang-box 通用匹配）是速度差距的来源 Kissinger 2020。
• 提取与传送：streaming_extract 按电路提取与 Pauli Flow的流条件把化简后的图变回线路，PyZX 作者在数千个随机电路与全部标准基准上未遇失败案例；不愿冒险时可用 teleport_reduce 原地优化 Kissinger 2020。
• 生态接口：支持 QASM/QC/Quipper 读写，可输出 TikZ；在 Jupyter 中即时可视化；也可作为命令行批处理优化器；内嵌 TODD 相位多项式优化器做配套 T-count 化简 Kissinger 2020。

开放挑战

NA104 结尾列出的挑战题至今仍部分有效 Kissinger 2020：其一，把 ancilla 引入图化简——彼时的 T-count 优化全部限于无 ancilla 情形，而相位多项式方法（如 TODD）恰恰靠借 ancilla 取益；其二，厘清提取的适用边界——启发式 streaming_extract 为何在数千个随机电路上从未失败，理论上仍无解释（参见电路提取与 Pauli Flow的硬度结果）；其三，把路由并入图形化简，让架构约束在 ZX 层面就被满足。此外还有 ZH 演算优化、图形演算做模拟与 lattice surgery 编译等方向。

• 面向中性原子：化简粒度与平台门集解耦——先用 ZX 把电路压到图状正规型，再把幸存的相位 gadget 映射为里德堡原生阻塞 CZ 门、Toffoli/CCZ 门或多控相位门（见多控相位门综合），这一”先图形化简、后原生门映射”的次序能避免把多体门过早分解成 CNOT 瀑布；编译产物再交给架构特定的映射与调度（如OLSQ-DPQA）。

结果对比

指标	数值	来源
可化简图规模	数十万顶点；数万顶点数秒级	Kissinger 2020
Clifford 化简吞吐	15 qubit / 2500 门 → 正规型 < 5 s（笔记本）	Kissinger 2020
T-count 单例	nth_prime（9 qubit）：567 T → 279 T，< 1 s	Kissinger 2020
张量验证上限	~10 qubit（32 位 Python）	Kissinger 2020
启发式化简 2Q 门	平均 $-19\%$（标准策略 $+22\%$），最高 $-40\%$	Staudacher 2023
与非 ZX 最优法组合	Adder8 总门数再降 $>15\%$、2Q 门 $>12\%$	Staudacher 2023
邻居解融合胜率	其启发式族中 $>70\%$ 电路取得最佳	Staudacher 2023

与其他概念的关系

• 规则与完备性的数学根基在ZX 演算；本文的化简器正是其可执行版本。
• 化简产生的图要回到线路，需要电路提取与 Pauli Flow；PyZX 的 streaming_extract 与 teleport_reduce 是两条工程路线。
• full_reduce 的相位 gadget 化简是T 计数与非 Clifford 约简的主力技术之一。
• “化简到恒等”验证策略的可靠性/完备性分析见电路等价性验证。
• 化简后图中的相位 gadget 可直接对准里德堡原生多控相位门综合，避免过度分解。
• 策略选择问题也可交给学习系统：见ZX 图的深度强化学习优化与Quarl：学习型线路优化器；跨编译器的公平评测框架见编译器公平评测与可视化。

参考文献

• A. Kissinger, J. van de Wetering, “PyZX: Large Scale Automated Diagrammatic Reasoning”, EPTCS 318, 229 (2020, QPL 2019). NA104 · DOI 10.4204/EPTCS.318.14
• R. Duncan, A. Kissinger, S. Perdrix, J. van de Wetering, “Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus”, Quantum 4, 279 (2020). NA102 · DOI 10.22331/q-2020-06-04-279
• K. Staudacher, T. Guggemos, S. Grundner-Culemann, W. Gehrke, “Reducing 2-QuBit Gate Count for ZX-Calculus based Quantum Circuit Optimization”, EPTCS 394 (2023). NA121 · DOI 10.4204/EPTCS.394.3
• 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
• K. Staudacher, L. Schmid, J. Zeiher, R. Wille, D. Kranzlmüller, “Multi-controlled Phase Gate Synthesis with ZX-calculus applied to Neutral Atom Hardware”, EPTCS 406, 96 (2024). NA122 · DOI 10.4204/EPTCS.406.5