电路提取与 Pauli Flow

化简过的 ZX 图长得不像任何电路，把它"翻译回"门序列的电路提取（circuit extraction）是一道分水岭：图上存在广义流（gflow）或更弱的 Pauli 流时，提取多项式时间可解；而一般幺正 ZX 图的提取已被证明是 #P-困难——化简自由度有多大，取决于你愿意被流条件约束多少。

问题背景

ZX 演算化简的代价是结构破坏：蜘蛛融合、支点变换会把整齐的门序列揉成一团任意拓扑的图。要在门型硬件上执行，必须把图重新变回电路——这就是电路提取问题：给定表示幺正算符 $U$ 的 ZX 图，产出实现 $U$ 的、规模可比的电路 de Beaudrap 2022。同一问题在测量式计算（MBQC / one-way model）里以另一种面目出现：把测量模式（measurement pattern）翻译成电路；两种翻译都依赖图上的因果流结构 Backens 2021。

对 ZX 编译流水线（PyZX 与图论化简）而言，提取是化简收益能否落袋的最后一公里：化简再漂亮，提取失败或提取出的电路暴涨，一切归零。

理论模型

开放图、测量平面与流

把 ZX 图抽象为标记开放图（labelled open graph）$(G,I,O,\lambda )$：$G$ 是无向图，$I/O$ 是输入/输出顶点，$\lambda$ 给每个非输入顶点标注测量平面（XY/XZ/YZ，纯 Pauli 测量是特例）。广义流（generalised flow, gflow）是一个纠正函数 $g:V\to 2^V$ 与次序 $\prec$，满足（对 XY 平面测量的 focused gflow） Backens 2021

$$v\in g(v),v\prec g(v),\mathrm{Odd}(g(v))=\{v\},$$

其中 $\mathrm{Odd}(S)=\{u:|N(u)\cap S|\text{为奇数}\}$。直观上：按 $\prec$ 的次序测量 $v$，对其纠正集 $g(v)$ 作用 $X$ 型 Pauli 即可确定性修复，依赖只流向”未来”。gflow 是 MBQC 确定性与电路可提取的图论刻画；保留全部三平面测量的版本称扩展 gflow（extended gflow） Backens 2021。

Pauli flow 是 Backens–Simmons 一系工作中更弱的条件：当已知某些顶点按 Pauli 基（X、Y 或 Z 单轴）测量时，纠正条件可以放宽——Pauli 测量无需”修复”，其结果可以传播进后续相位里。形式上 Pauli flow 把 $\mathrm{Odd}$ 条件按测量平面拆成分段的奇偶约束，并允许纠正集与被测顶点重合等 gflow 禁止的结构；因此凡有 gflow 者必有 Pauli flow，反之不然 Simmons 2021。放宽是有回报的：化简中大量 Pauli 测量顶点正是相位 gadget 化简的产物，Pauli flow 让这些图仍可提取。

提取算法与复杂度

NA111 给出首个支持三平面测量、且不引入 ancilla 的提取算法：反复对输出前沿（frontier）做高斯消元，把可确定的顶点逐一转为 CZ/CNOT 层；遇到 $YZ$ 标记的阻塞顶点时以支点变换绕开。其主要定理 Backens 2021：

$$\text{定理 5.5：}\text{含 gflow 的模式 }(n\text{入出},k\text{qubit})\stackrel{O(n^2{k}^2+k^3)}{\to }\text{等价的无 ancilla 电路}.$$

寻找流本身也是多项式的：gflow 判定 $O(|V{|}^3)$（Eslamy 等）到 $O(|V{|}^4)$，Pauli flow 判定 $O(|V{|}^5)$ Simmons 2021。Pauli flow 路线上，提取产物可组织成Pauli 依赖 DAG（PDDAG）——以 Pauli 旋转为节点、依赖关系为边的类电路结构，使每条图重写对电路指标的影响可精确模拟 Simmons 2021。

一般情形：#P-困难

流条件不可省略。NA112 证明 de Beaudrap 2022：

$$\text{CircuitExtraction 是 }\text{\#P}\text{-hard},\text{即便输出只是单 qubit、每只蜘蛛至多 3 条边的图}.$$

证明把 sat 归约到提取：布尔公式 $f$ 的解数 $N_1$ 决定某单 qubit 旋转 $X_{\alpha }$ 的角度 $\alpha =2\arcsin \sqrt{a_1/(a_{20}+a_{21})}$，能提取该图即能以 $2^n$ 比特精度确定 $N_1$。推论：若提取存在多项式算法，则 $\mathrm{P}=\#P$ 且多项式层级坍缩到第一层；近似提取、以及”图到采样输出”的翻译同样是 p-困难，任意这样的采样谕告都能概率地解 NP-完全问题 de Beaudrap 2022。因此实用系统（如 PyZX 的 streaming_extract）必须在”保持流”与”放手化简”之间权衡。

测量模式侧的重写

提取的对偶方向同样有用：NA111 把已知的一批测量模式重写规则统一到 ZX 记号下，并证明每条规则保持扩展 gflow 的存在性，于是可以在不破坏可提取性的前提下削减模式的 qubit 数——特别地，可以消除全部按 Pauli 基测量的 qubit Backens 2021。配套地，focused gflow 与”最大延迟 gflow”（maximally delayed gflow）被推广到多平面标记开放图，并给出了多项式时间的构造算法（逐步剥离输出层，单步 $O(n^3)$、总计 $O(n^4)$） Backens 2021。这套”保流重写 + 模式优化 + 提取”已实现于 PyZX，其无 ancilla 非 Clifford 门约简效果在当时达到最优水平 Backens 2021。

方法与实现

• 流保持的化简：与其提坏再救，不如化简时就保流。NA102 证明局域补图与支点变换保持 focused gflow，故 PyZX 化简后的图总可提取 Duncan 2020；NA118 把更强的因果流（causal flow, cflow）做成不变量，代价是规则子集更小、收益是”导线全程清晰、提取平凡” Holker 2023。
• cflow 保持优化的收益：flow-opt 在基准电路上平均降低 2Q 门 $19.8\%$，同时超越当时最优 ZX 策略（$14.6\%$）与非 ZX 策略 NRSCM（$18.5\%$）；把邻居解融合推广到多邻居后增益最大（$s_{\max }=4$ 时平均 $19.79\%$）；对 QFT 类电路可达每个非 Clifford 门恰好一个 2Q 门 Holker 2023。
• PDDAG 模拟：Pauli flow 提取把图重写映射为 PDDAG 上 Clifford 角旋转的移动，使化简策略的效果无需真正提取即可评估 Simmons 2021。
• 提取内嵌路由：提取默认假设全连通；NA111 建议把 ZX 路由算法并入提取，让电路在被提取时就适配受限连接 Backens 2021——这一步对连接性由物理决定的中性原子平台尤为关键。
• CNOT 重合成的双刃：提取过程会重合成（resynthesise）CNOT 网络，视输入不同可能大幅降低 2Q 门数，也可能反增 CNOT 计数；不重合成 2Q 门的策略（保持电路结构）可避免反增，代价是放弃部分化简收益 Backens 2021。对中性原子，由于 CZ 门即原生门，“保结构”版本往往更贴近物理成本模型。

与中性原子平台的关联：提取输出的 2Q 门逐一对应阻塞 CZ 门，门数与深度直接决定里德堡脉冲预算与误差预算；中性原子虽具长程阻塞与原子搬运能力（见布局映射与长程交互利用、原子搬运与相干输运），但搬运成本使”提取期路由”依然重要；cflow/Pauli flow 保证的清晰导线结构，也便于把相位 gadget 层直接替换为奇偶相位门等原生多体门。

参数与量级

量	数值/结论	来源
gflow 判定	$O(|V{|}^3)$（Eslamy 等）– $O(|V{|}^4)$	Simmons 2021
Pauli flow 判定	$O(|V{|}^5)$，多项式可识别	Simmons 2021
模式→电路（有 gflow）	$O(n^2{k}^2+k^3)$，无 ancilla	Backens 2021
一般幺正图提取	p-困难；多项式算法 $\Rightarrow \mathrm{P}=\#P$，PH 坍缩	de Beaudrap 2022
硬度实例规模	单 qubit 输出、蜘蛛至多 3 边即 p-困难	de Beaudrap 2022
cflow 保持优化	2Q 门平均 $-19.8\%$（ZX 前最优 $14.6\%$，NRSCM $18.5\%$）	Holker 2023
QFT 特例	每个非 Clifford 门恰 1 个 2Q 门	Holker 2023

与其他概念的关系

• 图与规则的来源是ZX 演算；化简策略与工程实现见PyZX 与图论化简，其中 streaming_extract 即本文流条件的生产级实现。
• 提取前后门数的变化决定了T 计数与非 Clifford 约简与 2Q 门优化的真实收益。
• 相位 gadget（相位 Gadget 与浅深综合）是化简图中的主要”居民”，提取时消化或保留它们是策略分水岭。
• 对中性原子：提取产物即阻塞 CZ 门网络；提取期路由与布局映射与长程交互利用、原子搬运与相干输运衔接；保留的多体相位结构可交给多控相位门综合。
• 提取正确性可用电路等价性验证闭环保障。

参考文献

• M. Backens, H. Miller-Bakewell, G. de Felice, L. Lobski, J. van de Wetering, “There and back again: A circuit extraction tale”, Quantum 5, 421 (2021). NA111 · DOI 10.22331/q-2021-03-25-421 · arXiv:2003.01664
• N. de Beaudrap, A. Kissinger, J. van de Wetering, “Circuit Extraction for ZX-Diagrams Can Be p-hard”, LIPIcs 229, art. 119 (ICALP 2022). NA112 · DOI 10.4230/LIPIcs.ICALP.2022.119 · arXiv:2202.09194
• W. Simmons, “Relating Measurement Patterns to Circuits via Pauli Flow”, EPTCS 343, 50 (2021, QPL 2021). NA110 · DOI 10.4204/EPTCS.343.4
• C. Holker, “Causal flow preserving optimisation of quantum circuits in the ZX-calculus”, preprint (2023). NA118
• 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