Quartz 超优化｜中性原子量子计算知识库

Quartz 不再让专家手写优化规则：它枚举小电路、用 SMT 求解器验证等价、自动生成整套"等价替换类"，再以代价回溯搜索把替换类组合施加上千次——对三种真实处理器门集，26 个基准电路平均门数削减 29%–49%，全面追平或超越手工调优的编译器。

问题背景

主流量子编译器（Qiskit、t|ket⟩ 等）依赖专家设计的电路变换规则，贪心地”见规则就应用”。这条路有两个先天缺陷 Xu 2022：其一，规则设计耗费人力，且手工难找的微妙等价（如跨门融合旋转角）会被错过；其二，规则与门集绑定——为 IBMQX5 的 ${U_{1}, U_{2}, U_{3}, CNOT}$ 写的规则不能用于 Rigetti Agave 的 ${R_{x} (\pm π /2), R_{z}, C_{Z}}$ ，而新兴硬件（含中性原子的多比特原生门集）还在不断产出新门集。

超优化（superoptimization）换一种思路：不给规则，自动搜索并机器验证规则。Quartz 把经典超优化器 TASO 的”自动生成 + 验证 + 回溯搜索”三段式搬进量子世界，并把表示能力推广到带连续参数的门 Xu 2022。它与 T 计数与非 Clifford 约简的专门算法、Quarl：学习型线路优化器与RL 线路优化等学习类方法同属”超越手写规则”的谱系。

理论模型

符号电路与等价替换类

为覆盖参数化门（ $R_{z} (θ)$ 、 $U_{3} (θ, ϕ, λ)$ 等），Quartz 引入符号量子电路：门参数是形式变量 $θ, ϕ, λ, \dots$ ，替换两端允许参数的算术表达式（如把 $R_{z} (ϕ)$ 与 $R_{z} (θ)$ 融合为 $R_{z} (θ - ϕ)$ ）。两个符号电路等价，当且仅当对参数的一切取值它们实现同一幺正 Xu 2022。

替换（transformation）：一对符号电路 $(C_{T}, C_{R})$ ，含义是”匹配 $C_{T}$ 的子电路可换成 $C_{R}$ ”；
等价替换类（ECC, equivalent circuit class）：彼此等价的电路集合，类内任意两电路都构成合法替换。一整套 ECC 就是该门集的自动”规则手册”；
$(n, q)$ -完备性：若 ECC 集覆盖了至多 $n$ 个门、至多 $q$ 个 qubit 的所有电路之间的等价，则称 $(n, q)$ -完备。它是替换集覆盖度的可校验指标。

生成、验证与搜索

Quartz 流水线三阶段 Xu 2022：

电路生成（RepGen）：从 $(j - 1, q)$ -完备集迭代构造 $(j, q)$ 候选；用”代表元”去重，把待验证的电路数削减一到三个数量级；
等价验证：等价性归约为量词自由非线性实算术上的 SMT 问题，交由 Z3 求解——对参数化门，等价要求对全部参数取值成立，SMT 语义恰好精确对应（对所考察门集，无需量化词交替的一般形式）。实现上的关键一步是消去三角函数：常数角用 $sin (π /4) = 2 /2$ 等闭式代入，变量角则引入新变量 $s_{t}, c_{t}$ 并附加约束 $s_{t}^{2} + c_{t}^{2} = 1$ ，替换 $sin (t), cos (t)$ 后整个等价查询化为有限域上的多项式约束 Xu 2022；
代价回溯搜索：以门数为目标代价 $C os t (\cdot)$ ，把当前电路的所有可应用替换 $Apply (C, T)$ 放入按代价排序的优先队列，带回溯与去重（已见集合 $D_{see n}$ ）地迭代；超参数 $γ$ 控制搜索的激进度，权衡时间与解质量。搜索作用于逻辑优化阶段，即 qubit 映射之前 Xu 2022。

生成的替换集不仅覆盖了已有优化器的全部手工规则，还包含手工未发现的新替换 Xu 2022。指数增长的搜索空间由”门数 $n$ 取小值”控制：实验取 $n = 6/4/3$ （配合 $q = 3$ ）即可产生足够有用的替换 Xu 2022。

分块综合的放大器：QGo

替换类只改局部。QGo 把”自动综合”放大到全电路：将电路划分为相互独立的 $k$ -qubit 块（ $k < n$ ），每块经幺正综合重生成（块内综合由拓扑感知的搜索树式综合器完成，可处理至多 4 qubit），再拼接回整路；把对整路的 $O (exp (n))$ 综合摊成线性数量次的 $O (exp (k))$ 调用 Wu 2020。块大小的权衡直接：更大块带来更多 CNOT 削减，但 5-qubit 块的综合求解时间已显著拉长，3/4-qubit 块是实验上的甜点（QGo-3/QGo-4）。QGo 含物理 qubit 映射、线路划分、量子综合与电路重组四个模块，与任意映射器可组合（作者以 t|ket⟩ 的映射器做了敏感性实验：映射质量与优化收益正相关，高度互联的块划分最佳），是首个把综合成功嵌入大规模编译工具链的演示 Wu 2020。

代价回溯搜索的细节

优化阶段的搜索是替换类价值的”兑现环节” Xu 2022：

优先队列驱动：从输入电路 $C_{in}$ 出发，反复弹出代价最低的电路，施加全部可用替换得到 $Apply (C, T)$ ，去重（ $D_{see n}$ 集合）后压回队列，同时维护当前最优 $C_{b es t}$ ；队列空或超时则终止；
超参数 $γ$ ：代价大于 $γ \times$ 当前最优代价的候选直接剪除—— $γ = 1$ 退化为纯贪心，放宽 $γ$ 则以时间换逃离局部极小的能力。图 6 的实例很说明问题：在 $gf 2^{4} - mult$ 电路上一条交换 CNOT 控制/靶位的替换序列，前三次替换都不降门数、第四次才兑现净收益——这正是贪心规则流会错过的优化 Xu 2022；
代价即门数：以总门数为目标代价；优化发生在逻辑电路层面（qubit 映射之前），因此结果与具体硬件拓扑解耦，可与后续映射器自由组合；
可组合的预处理：旋转合并、Toffoli 分解等标准步骤作为前端，替换搜索负责它们覆盖不到的跨门等价。

搜索空间的代价

替换类的覆盖度与成本是一对硬权衡：候选电路数 $∣ R_{n} ∣$ 随门数 $n$ 指数增长， $(n, q)$ -完备集的生成与验证需要数小时量级的算力；而替换集的大小又直接决定优化器的搜索空间与最终收益。Quartz 的应对是把 $n$ 压到”刚好够用”（Nam/IBM/Rigetti 分别取 $n = 6/4/3$ 、 $q = 3$ ），并依赖 RepGen 的代表元去重把验证规模压低一到三个数量级 Xu 2022。这一”生成一次、反复使用”的摊销结构，与每次都要现场搜索的学习类方法（Quarl：学习型线路优化器）形成对比。

Quartz 三阶段流水线：电路生成 RepGen → 等价验证（Z3）→ 代价回溯搜索，右下角示意 ECC 内的替换应用（图源：Xu 2022 Fig. 1）

方法与实现

三种门集的 ECC 生成：Nam（ $H, X, R_{z}, CNOT$ ）、IBM（ $U_{1}, U_{2}, U_{3}, CNOT$ ，源自 IBMQX5）、Rigetti（ $R_{x} (\pm π /2), X, R_{z}, CZ$ ，源自 Agave）；在 128 核上30 分钟内完成生成 + 验证 Xu 2022。
预处理：旋转合并与 Toffoli 分解先行；Rigetti 的 CZ 门集需先把 CNOT 改写为 $H CZ H$ ，再把 $X, H$ 转译为 $R_{x} / R_{z}$ 序列——门集转译与替换搜索解耦 Xu 2022。
评测：26 个基准电路（含 Toffoli 分解、Galois 域乘法器、QFT、CCX/CCZ 等），以总门数为代价；生成的替换集覆盖了既有优化器使用的全部手工规则，并包含手工未发现的新替换 Xu 2022。
QGo 规模实验：QGo 的验证覆盖三个尺度——小电路在真机（IBM Athens）上看保真度、中等电路在噪声模拟上看保真度、大电路（60+ qubit）在解析模型上看 CNOT 静态削减；大电路映射到 $8 \times 8$ 二维格点，QGo-3/QGo-4 对应 3/4 qubit 块；小块综合耗时长于贪心规则，但可离线换深度缩减 Wu 2020。
实现可用性：Quartz 以开源项目发布并附 PLDI 工件；门集、 $(n, q)$ 与代价函数均为显式参数，为新平台（如中性原子原生门集）生成专属替换类无需改动搜索与验证代码 Xu 2022。
对中性原子平台的意义：Quartz 的门集无关性意味着可以为目标门集重新生成一整套 ECC——中性原子的原生集是单比特旋转 + 阻塞 CZ 门/Toffoli-CCZ 门乃至任意规模受控相位（见多控相位门综合、Geyser：原生多比特门编译），而非通用的 CNOT 门集；这正是现有编译器规则最少覆盖、ECC 自动生成最有增量价值的场景。超优化后的电路再进入布局与搬运调度（布局映射与长程交互利用），其正确性由电路等价性验证闭环。

结果对比

Quartz 与 QGo 是同一思路（自动综合）的两个尺度：前者离线生成替换类、在线搜索，后者把块级综合摊销到全电路。关键数字汇总如下。

指标	数值	来源
ECC 生成+验证耗时	< 30 分钟（3 门集，128 核）	Xu 2022
RepGen 去重	候选电路数减少 1–3 个数量级	Xu 2022
平均门数削减（Quartz）	Nam/IBM/Rigetti： $29%/30%/49%$	Xu 2022
既有优化器同基准	$27%/23%/39%$	Xu 2022
$(n, q)$ 设置	$n = 6/4/3$ ， $q = 3$ （Nam/IBM/Rigetti）	Xu 2022
QGo CNOT 削减	平均 $29.9%$ ，最高 $50%$ （对比 t\|ket⟩）	Wu 2020
QGo 块综合上限	块级综合可处理至多 4 qubit，5-qubit 块求解时间过长	Wu 2020
QGo 大规模（60+ qubit）	QGo-3/4 平均 $22.8%/28.9%$	Wu 2020
QGo 保真度验证	IBM Athens 实机增益；实测-模拟相关性 $98%$	Wu 2020

与其他概念的关系

Quartz 只做局部替换，PyZX 与图论化简与ZX 演算的图形化简则是另一条自动重写路线，二者可级联（先图形压结构、后替换类修细节）。
生成的门集无关替换与中性原子原生门结合是开放方向：见Geyser：原生多比特门编译与多控相位门综合。
优化正确性由自动定理证明器（生成期）与电路等价性验证（编译末期）双重保障。
搜索策略的手写规则可被学习取代：Quarl：学习型线路优化器、RL 线路优化与ZX 图的深度强化学习优化。
门数/深度指标的取舍与评测方法学见通用量子基准套件与编译器公平评测与可视化。

参考文献

M. Xu, Z. Li, O. Padon, S. Lin, et al., “Quartz: Superoptimization of Quantum Circuits”, Proc. 43rd ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI) (2022). NA116 · DOI 10.1145/3519939.3523433 · arXiv:2204.09033
X.-C. Wu, M. G. Davis, F. T. Chong, C. Iancu, “QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis”, preprint (2020). NA105 · arXiv:2012.09835
Z. Li, J. Peng, Y. Mei, S. Lin, et al., “Quarl: A Learning-Based Quantum Circuit Optimizer”, Proc. ACM Program. Lang. (2024). NA130 · DOI 10.1145/3649831
T. Patel, D. Silver, D. Tiwari, “Geyser: a compilation framework for quantum computing with neutral atoms”, ISCA (2022). NA012 · DOI 10.1145/3470496.3527428
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

中性原子百科

探索

Quartz 超优化