关于POPQC：一种量子电路并行优化算法的学术报告
本研究题为《POPQC：面向量子电路的并行优化》，由来自卡内基梅隆大学（Carnegie Mellon University）的研究团队完成。论文作者为Pengyu Liu、Jatin Arora、Mingkuan Xu和Umut A. Acar。该研究已于2025年7月28日至8月1日在美国波特兰举行的第37届ACM并行算法与架构研讨会（SPAA ‘25）上被接收，并收录于会议论文集中。
一、 研究背景
本研究的领域属于量子计算与计算机科学算法的交叉领域，具体聚焦于量子电路的优化问题。量子计算机通过量子比特（Qubit）和量子门（Gate）构成的电路来执行计算。然而，当前的量子硬件（常被称为“嘈杂中型量子”（Noisy Intermediate-Scale Quantum， NISQ）时代设备）存在退相干、门操作不完美等噪声问题，限制了可执行电路的规模和保真度。因此，对量子电路进行优化以减少门数量、降低电路深度（Depth）变得至关重要，这不仅能提升计算效率，还能在有限的相干时间内完成原本不可能的计算。
然而，量子电路的全局优化被证明是QMA-困难的，这是一个计算上极其困难的问题。因此，现有的优化器大多依赖于启发式方法，存在计算时间长（通常为超线性甚至指数时间）、无法保证优化质量、且算法本质上是串行的等挑战。随着量子计算向“容错应用规模量子”（Fault-tolerant Application-scale Quantum， FASQ）时代迈进，处理数百万门级的大型电路对优化器的效率和可扩展性提出了更高要求。先前的工作（Arora等人， 2025）提出了“局部最优性”（Local Optimality）的概念，通过保证电路中每个连续的ω段（即包含ω个门的子电路）相对于一个称为“预言机”（Oracle）的外部优化器是最优的，从而在保证一定质量的前提下提高效率。但其算法仍是串行的，且存在二次开销。
因此，本研究旨在解决量子电路优化中的并行性难题。其核心目标是：设计并实现一个高效的并行算法，该算法能够在保证“局部最优性”这一质量属性的前提下，充分利用现代多核处理器的计算能力，实现对大型量子电路的快速优化，从而克服现有串行优化器在面对大规模电路时速度慢、难以扩展的瓶颈。
二、 研究方法与工作流程
本研究提出了一种名为POPQC（Parallel Optimization for Quantum Circuits）的全新并行优化算法。其核心工作流程并非传统的实验流程，而是算法设计、理论分析、实现与评估的系统性工程。主要“研究过程”可概括为以下几个关键步骤：
1. 并行算法设计： 研究首先设计了一个不依赖于传统“切割-融合”（Cut-Meld）操作的并行算法。算法的核心思想是维护一个指向电路内部位置的“指针”（Finger）集合，并保持一个关键不变性：任何未被优化的ω段电路至少包含一个指针。算法以轮次（Rounds）进行： * 指针选择（SelectFingers）： 在每一轮开始时，算法从当前指针集合中选出一组“互不干扰”的指针（即任意两个指针之间至少间隔2ω个门）。这确保了围绕这些指针的优化可以并行执行而不会相互冲突。算法通过将电路划分为大小为2ω的组，并巧妙地从奇数组或偶数组中选取首个指针，保证总能选出至少1/(4ω)比例的指针进行优化。 * 并行段优化： 对于每个被选中的指针，算法以其为中心，从电路中提取一个大小为2ω的段（包含指针前后各ω个门）。然后，并行地将这些段提交给一个外部的“预言机”优化器（例如VOQC、Quartz等）进行优化。预言机被视为一个黑盒函数，负责对小段电路进行高质量的（通常是计算密集型的）优化。 * 更新电路与指针： 如果预言机优化了某个段（减少了其门数量），算法会用优化后的段替换原段，并在优化段的两个边界处插入新的指针，因为边界区域可能与相邻段产生新的优化机会。如果预言机未做优化（说明该段已相对于预言机最优），则简单地移除该指针。这一步骤并行地生成新的指针集和电路更新集合。 * 应用更新与合并指针： 算法并行地将所有优化后的段更新到主电路数据结构中，并将新生成的指针与未被选中的旧指针合并、去重，形成下一轮的指针集。 * 迭代终止： 重复上述步骤，直到指针集合为空。此时，不变性保证了电路中不再存在未被优化的ω段，即电路达到了局部最优。
2. 高效并行数据结构开发： 为了支持算法中频繁的随机访问（如根据逻辑序号获取第i个门）、插入/删除（门被优化掉）以及并行更新，研究团队专门设计了一种基于“索引树”（Index Tree）的量子电路并行数据结构。该结构底层使用数组存储门，被删除的门用“墓碑”（Tombstone）标记。索引树是一个完全二叉树，其中每个叶子节点对应一个门（或墓碑），权重为1（有门）或0（墓碑）；内部节点的权重是其子树中非墓碑门的数量。这一设计使得before（查询某索引前有多少非墓碑门）和get（获取第i个非墓碑门）等关键操作可以在O(log n)的工作量和跨度（Span，即并行时间）内完成，而substitute（批量替换门）也能高效并行执行。这是本研究实现高效并行操作的核心技术贡献之一。
3. 理论分析： 研究对POPQC算法进行了严格的理论分析，证明了其正确性和效率。 * 正确性证明（定理7）： 通过形式化论证，证明了只要初始指针集满足不变性（研究中使用从0开始每ω间隔放置指针的简单初始化），且预言机是“行为良好”的（优化后的输出段自身也是局部最优的），那么POPQC算法最终输出的电路必定满足局部最优性。 * 效率证明（定理4）： 分析了算法的工作量（Work，即串行总时间）和跨度（Span，即关键路径长度，衡量并行潜力）。证明得出：假设ω为常数，预言机处理2ω段的工作量为W、跨度为S，则POPQC的总工作量为O(n (ω log n + W))，总跨度为O(r (log n + S))，其中n为电路大小，r为算法运行的轮数。在实践中，ω和W可视为常数，因此工作量接近O(n log n)，跨度主要取决于轮数r乘以对数因子。
4. 系统实现与实证评估： 研究团队使用Rust编程语言和Rayon并行库实现了POPQC算法。为了评估其“在实际中的有效性”，他们设计并执行了一系列基准测试。 * 评估对象（研究样本）： 选取了来自PennyLane、Qiskit、NWQBench等标准测试集的多种量子算法电路作为基准，包括布尔可满足性问题（BoolSat）、二叉焊接树（BWT）、Grover搜索算法、HHL线性方程求解算法、Shor整数分解算法等。这些电路的规模（门数量）从数千到数百万不等，具有挑战性。 * 对比对象（对照组）： 主要与当前最先进的串行优化器VOQC进行比较，同时也与同样追求局部最优性的串行优化器OAC进行对比，以分离并行性和算法改进各自带来的收益。 * 实验设置： 在一台64核（AMD EPYC 7763）、256GB RAM的服务器上运行。为POPQC选择参数ω=200，并使用VOQC作为默认的预言机优化器。 * 评估指标： 主要测量运行时间和优化质量（以门数量减少的百分比表示）。此外，还评估了可扩展性（随核心数增加的速度提升，即自加速比）、工作效率（与最佳串行算法OAC相比的单线程性能）、算法轮数r、灵活性（更换预言机为Quartz并优化电路深度）等。
三、 主要结果
实证评估获得了多方面的重要结果，数据有力地支持了研究的核心主张：
性能与质量： 如表1所示，在64线程上运行的POPQC与单线程VOQC相比，在几乎所有测试电路上都取得了数量级的加速（平均加速比超过1000倍，部分案例超过10000倍）。更重要的是，这种巨大的性能提升并未以牺牲优化质量为代价。在大多数基准测试中，两者优化后的门数量减少百分比（Gate Reduction）相差无几（通常在0.5%以内），甚至在HHL等个别案例中，POPQC的质量还优于VOQC（研究者分析是因为POPQC的迭代特性可能捕捉到了VOQC单次遍历遗漏的优化机会）。
局部最优性的效率贡献： 为了区分并行性和算法本身（局部最优性）带来的收益，表2比较了单线程POPQC和单线程VOQC的运行时间。结果显示，即使在不使用并行的情况下，POPQC也平均比VOQC快70倍以上。这证明了基于局部最优性和新型指针追踪的算法设计本身，相比传统的全局启发式或串行局部优化方法，具有显著的效率优势。
并行可扩展性： 图3和图5展示了POPQC在不同核心数下的自加速比。结果显示，对于大多数大型电路（如HHL、BWT、StateVec等），算法能够很好地扩展到数十个核心，在64核上获得20倍以上的加速。可扩展性随着电路规模的增大而提高，说明POPQC非常适合处理大规模问题。对于少数规模较小或优化轮数较多的电路（如VQE、BoolSat），可扩展性相对较低，这符合并行计算中粒度控制的理论预期，也提示了未来优化的方向。
工作效率： 如表3所示，即使以单线程模式运行，POPQC在大多数情况下也优于同样保证局部最优性的串行基线优化器OAC，且随着电路规模增大优势更明显。这是因为POPQC避免了OAC算法中二次开销的“切割-融合”操作，其索引树数据结构更为高效。此外，分析表明POPQC超过90%的时间花费在调用预言机上，说明算法自身的“管理开销”很低，是工作高效的。
算法行为验证： 图4显示，在所有基准测试中，算法收敛所需的轮数r是一个较小的常数（通常在20到130之间），且随电路规模增长缓慢。这验证了理论分析中关于r值的乐观假设，解释了为何实际跨度较低、并行性得以有效发挥。它也反映了量子电路固有的局部性特征。
灵活性验证： 如图6所示，研究者成功将POPQC与另一个优化器Quartz集成，并使用分层（Layered）电路表示来优化以深度（Depth）为主要目标的混合成本函数。实验表明，POPQC能够有效地利用Quartz进行深度优化，在部分电路上实现了显著的深度削减，而门数量仅有小幅增加。这证明了POPQC框架的通用性，它不依赖于特定预言机或成本函数。
四、 结论与意义
本研究成功提出、理论分析、实现并全面评估了POPQC——首个为量子电路优化提供的、具有严格质量保证（局部最优性）的高效并行算法。其核心结论是：量子电路的并行优化不仅是可行的，而且可以带来极致的性能提升，同时保持甚至提升优化质量。
研究的科学价值和应用价值体现在： * 算法理论贡献： 提出了一个新颖的并行算法范式，通过指针集和不变性来替代传统的顺序滑动窗口优化，并设计了支持高效并行更新的索引树数据结构。相关的正确性证明和复杂度分析为后续研究奠定了基础。 * 解决实际瓶颈： POPQC首次使在数秒或数分钟内优化数百万门级的大型量子电路成为可能，而现有优化器可能需要数小时甚至数天也无法完成。这直接解决了NISQ和未来FASQ时代量子软件工具链中的一个关键性能瓶颈。 * 推动量子软件发展： 该研究指明了量子电路优化器向并行化、高性能化发展的可行路径。其开源实现为社区提供了一个强大的新工具，并设定了新的性能基准。 * 通用性框架： POPQC作为一个算法框架，可以与任何现有的或未来的“预言机”优化器（无论是基于规则、搜索还是重综合）相结合，从而继承预言机的优化能力并赋予其并行性和可扩展性。
五、 研究亮点
六、 其他有价值内容
论文还对量子计算基础（量子态、门、电路表示）、相关工作（包括基于规则、搜索、重综合、近似优化等多种技术路线）进行了清晰的梳理，为读者提供了完整的背景。研究者也坦诚讨论了算法的局限性，如对于某些特定结构的电路（可能导致轮数r较大），并行加速可能会受限，这为未来研究指出了方向。所有代码已在GitHub上开源，促进了可重复性和进一步的研究。