关于量子电路优化新方法Quasar的学术研究报告
本文旨在向中文科研界介绍一项发表于2026年《Proceedings of the ACM on Programming Languages》（Proc. ACM Program. Lang.）期刊PLDI会议上，题为《Equality Saturation for Quantum Circuit Optimization》的原创性研究。该研究由来自哥伦比亚大学的杨甘祥（Ganxiang Yang）、荣辉谷（Ronghui Gu）以及马里兰大学的Paige Raun、Runzhou Tao共同完成，提出了一种名为Quasar的新型量子电路优化器，其核心创新在于将“等价饱和”（Equality Saturation）技术首次系统性地应用于量子电路优化领域，旨在解决传统顺序优化方法因搜索空间有限而导致的次优解问题。
一、 研究背景与目标
量子计算在化学模拟、材料科学等领域展现出革命性潜力，但其实际应用受限于当前量子操作的噪声和成本。因此，减少量子电路中的操作数量（门数、深度）是提升计算保真度的关键，而电路优化正是连接理论潜力与实际执行的关键桥梁。
量子程序通常表示为量子电路，优化过程涉及应用一系列保持功能等效的电路重写规则（例如门消除、交换律应用），以生成成本（如门计数、电路深度）更低的等效电路。然而，现有优化器（如IBM Qiskit、TKET以及基于搜索的超优化器Quartz、QESO、GuoQ）大多采用顺序重写策略：每个重写作用于前一个重写产生的电路。这种方法存在两个长期存在于经典程序优化中、但在量子电路优化中仍未解决的固有难题： 1. 阶段排序问题（Phase-ordering Problem）：重写规则的应用顺序至关重要。如图1所示，不合适的顺序（如先应用t3而非t2）可能导致优化陷入局部最优，无法达到最佳效果。 2. 规模增大重写问题（Size-increasing Rewrites）：某些优化路径需要暂时引入额外的门（如图1中的t1），以创造后续优化机会（如t4的相邻CX门对消除）。顺序优化器通常因其启发式策略或巨大的规则集而难以探索此类路径。
现有方法通过扩大规则集（至上万甚至百万条规则）来提升优化能力，但这加剧了搜索的复杂性。因此，本研究的目标是开发一种能够系统性地探索巨大等效电路空间，并在给定重写迭代步数限制内，找到可达最优电路的新方法。
二、 Quasar工作流程详述
Quasar的核心思想是将电路优化形式化为在等价图上的搜索问题，通过“等价饱和”技术同时而非顺序地应用重写规则，从而有效探索优化空间。其工作流程包含四个主要步骤，并涉及两种互补的电路表示方法。
步骤一：原子重写规则推断 为了在保持强大优化能力的同时提升效率，Quasar首先从庞大的现有规则集（如从Quartz和QESO收集的共22,546条规则）中，推断出一个紧凑的原子规则集。 * 研究目标与方法：目标是获得一个规模小、易于高效应用，且与原始规则集“表达能力等价”的规则集。所谓“原子规则”，是指无法由其他规则组合而成的基本规则。 * 处理流程：算法分为两个阶段。首先，在给定的量子比特数和门数界限内（如≤4个量子比特，规则单边≤3个门），枚举所有可能的等效电路对，形成一个基础原子规则集。其次，按左项长度递增的顺序处理输入规则集（𝑅𝐼）中的每条规则。对于每条待考察规则(ℓ → 𝜌)，算法使用等价饱和技术进行检查：构建一个以ℓ为起点的E图，并用当前原子规则集𝑅进行饱和。如果在饱和后的E图中能找到𝜌，则说明该规则可由𝑅中的规则组合而成，是冗余的，予以跳过；否则，将其加入𝑅。此过程确保了最终输出的原子规则集𝑅既紧凑（仅40条规则），又与原始庞大规则集在优化能力上等效。
步骤二：初始化双E图表示 Quasar接受用户输入的量子电路，并将其同时初始化为两种互补的E图表示，以利用各自优势： 1. 序列E图（seq-eg）：将电路线性化为门序列，使用“then”操作符连接。这种表示提取速度快，贪婪提取算法在加法成本模型下能保证最优。 2. 有向无环图E图（dag-eg）：将电路表示为其固有的依赖有向无环图，其中节点为量子门，边为量子线。这种表示更紧凑，能天然避免无关门之间的组合性交换问题，但提取过程更复杂。
步骤三：探索阶段——等价饱和 在初始化E图后，Quasar进入探索阶段，迭代地对两种E图应用原子重写规则集。 * 在seq-eg上的应用：重写规则被编码为单根项重写。匹配规则左项后，将右项作为新节点插入，并与源项所在等价类合并，从而记录等价关系而不删除原有项。如图8所示，通过应用规则（如r1：CX与相邻X门交换，r2：相邻X门消除），E图逐渐扩展，包含越来越多的等效电路变体。 * 在dag-eg上的应用：重写规则被编码为图重写模式。为处理图匹配可能产生的语法有效但语义无效的重写（例如，匹配到的变量节点实际上作用于同一量子比特），Quasar采用了语法-语义解耦策略。在探索阶段，仅执行轻量级的语义约束检查：为每个E节点推断其操作的量子比特，并在应用重写前检查匹配变量的量子比特约束。复杂的全局语义验证则被推迟到提取阶段。这避免了每次重写后进行昂贵验证的开销，是提升可扩展性的关键设计。 * 调度式等价饱和：为解决规模增大重写规则导致E图爆炸性增长的问题（如图13所示），Quasar引入了调度式等价饱和算法（算法2）。其核心是“提取-重建”循环：在探索一定步数后，提取当前最优图，并以其为起点重建一个新的E图重新开始饱和。这能有效剪枝搜索空间中不贡献成本降低的冗余区域，在实践中比在臃肿的E图上继续探索更快找到优质解。
步骤四：提取阶段——最优电路选择 探索阶段结束后（达到饱和、步数限制或超时），Quasar从E图中提取一个在指定成本模型下成本最低的电路。 * seq-eg提取：采用基于项的贪婪提取算法。由于seq-eg的表示和加法成本模型（如总门数、2-qubit门数），该贪婪算法被证明能保证提取出E图中的全局最优电路（定理1）。 * dag-eg提取：由于2-qubit门节点共享和提取原子性（选择CX节点必须同时选择其关联的fst和snd节点）等问题，贪婪提取会高估成本或产生无效电路。因此，Quasar将dag-eg的提取问题形式化为一个整数线性规划问题。该ILP模型定义了选择变量、成本目标函数，并施加了根节点选择唯一性、子节点一致性、输入节点必选、2-qubit门提取原子性以及DAG拓扑排序等约束。求解此ILP可保证得到语义有效且成本最优的电路。 * 序列重排序优化：针对seq-eg在处理高并发电路时，因需要枚举大量无关门交换而导致搜索空间膨胀的问题，Quasar在构建seq-eg之前，引入了一个预处理步骤：通过求解另一个ILP问题，寻找一个使DAG中相邻门在序列中距离最小的门排序。这种“序列重排序”能显著减少探索初期所需的交换操作，提升优化效率（图19b）。 * 组合策略：Quasar并行运行seq-eg和dag-eg，并定期交换当前最优解，形成组合策略，以充分利用两者在搜索效率和表示紧凑性上的互补优势。
三、 主要实验结果
研究在包含10个基准套件、总计176个多样化的量子电路上评估了Quasar，并将其与当前最先进的优化器（Qiskit, TKET, Quartz, QESO, GuoQ）进行了全面比较。评估指标包括加法成本模型下的2-qubit门减少率、总门减少率、保真度提升，以及非加法成本模型下的电路深度减少率。 * 优化质量：在IBM门集下，Quasar取得了几何平均的显著提升：2-qubit门数减少20.2%，总门数减少33.5%，电路深度减少24.2%，保真度提升21.4%。在所有对比优化器中，Quasar在75%、92%、62%和80%的电路上分别于上述四个指标上达到最优或持平。研究中的图15、图16清晰展示了Quasar相对于基线方法的优势，特别是在许多基线方法陷入零改进的电路上，Quasar找到了有效的优化路径。 * 性能与效率：图18的质量-时间前沿曲线显示，Quasar在达到更高最终优化质量的同时，收敛速度也快于基于搜索的超优化器。启发式优化器（Qiskit, TKET）虽快但很快达到平台期。 * 组件分析： * 原子规则集：图20表明，使用40条原子规则的Quasar，在大多数时间点上都优于使用数千条组合规则或原始数万条规则集的版本，证明了原子规则集在保持表达能力的同时极大提升了探索效率。 * 双E图优势：图17通过两个具体案例（csla_mux_3和radd_250）展示了seq-eg和dag-eg的互补性。前者在紧凑表示上更有效，后者则在高吞吐量探索上占优。两者结合贡献了Quasar的整体优势。 * 优化技术有效性：消融研究（图19a, 19b）证实，调度式等价饱和和序列重排序技术分别显著改善了58%/80%和58%/79%的基准电路在2-qubit门和总门减少率上的表现。
四、 研究结论与意义
本研究成功提出并实现了Quasar，第一个基于等价饱和的量子电路优化器。其主要结论与价值在于： 1. 方法论创新：首次将等价饱和系统引入量子电路优化，为解决长期存在的阶段排序和规模增大重写问题提供了全新且强大的框架。该框架能够在用户指定的重写步数限制内，理论保证找到可达的最优电路（在已探索的E图空间内）。 2. 关键技术贡献：提出了原子规则推断、双E图表示（seq-eg与dag-eg）、语法-语义解耦的DAG验证、调度式等价饱和、序列重排序以及针对DAG的ILP提取等一系列创新技术，共同确保了优化的正确性、可扩展性和高效性。 3. 显著性能提升：实验证明，Quasar在多个关键指标上全面超越或匹配现有最先进的优化器，特别是在传统方法难以改进的电路上取得了突破，为量子电路在近期的噪声中级量子（NISQ）设备上实现更可靠、更低成本的运行提供了强有力的工具。 4. 为社区提供新工具与思路：Quasar的开源实现为量子编译社区提供了一个新的高性能优化基准。其基于E图的优化范式也为未来结合机器学习（如强化学习指导规则选择）等进一步探索更优、更深的优化路径指明了方向。
五、 研究亮点
六、 其他有价值内容
本文还对相关工作进行了全面梳理，明确了Quasar相对于传统固定序列优化器、基于搜索的超优化器（如Quartz、QESO）、基于机器学习的调度器（如Quarl）以及基于ZX演算的优化器（如PyZX）的差异与优势。同时，文章详细阐述了背景知识，包括量子电路、重写规则、E图与等价饱和的基本概念，使得不熟悉该领域的读者也能理解其工作。文中的大量图示（如图1、2、6、8、9、11、14）非常直观地解释了关键问题和解决方案，增强了论文的可读性。