这篇题为《there and back again: a circuit extraction tale》的文档是由Miriam Backens (University of Birmingham)、Hector Miller-Bakewell与Giovanni de Felice (University of Oxford)、Leo Lobski (ILLC, University of Amsterdam (until 2020))以及John van de Wetering (Radboud University Nijmegen)共同完成的研究论文。该论文于2021年3月25日发布，并已被期刊《Quantum》接受。

研究领域与学术背景

本研究属于量子计算领域，具体聚焦于量子计算的实现模型之间的转换与优化。量子计算主要有两种基础实现模型：基于量子门的电路模型（gate-based model）和基于测量的单向量子计算模型（measurement-based one-way model）。前者通过一系列幺正的（可逆的）单比特和两比特门进行计算，而后者则通过对一个预先制备好的特定资源态（通常是图态）进行适应性测量来执行计算。

这两种模型各有优势，并在不同场景下（如算法验证、电路优化、资源最小化）具有互补价值。因此，在这两种模型之间建立高效、精确的转换算法至关重要。转换过程的一个核心概念是“广义流”（generalized flow, gflow），它为一个特定的“标记开放图”（labelled open graph，描述了图态结构和测量平面）能够确定性地实现量子计算提供了充分必要条件。过去的大量研究集中在所有测量都限制在布洛赫球的xy平面上的情形。然而，允许在所有三个平面（xy， xz， yz）进行测量通常可以生成包含更少量子比特、结构更简单的测量模式（measurement pattern），从而提供更多的优化可能性。尽管“扩展广义流”（extended gflow）的概念已被提出用于处理多平面测量，但在此之前，如何从具有扩展广义流的测量模式中高效地提取出对应的量子电路，一直是一个未解决的难题。

本研究的核心目标是填补这一空白。研究者旨在开发第一个能够从包含所有三个平面测量且具有扩展广义流的单向量子计算模型中提取量子电路的通用算法。该算法将不引入辅助比特，并且具有高效性。

研究详细流程与方法

本研究并非一个包含实验样本的传统实验科学流程，而是一个理论计算机科学与数学物理领域的理论研究。其“工作流程”本质上是一系列定义、定理证明、算法设计与验证的过程。研究的核心“对象”是数学结构：标记开放图、ZX演算（ZX-calculus）图、测量模式和量子电路。研究的“处理与分析”过程是通过形式化推导和图变换规则来完成的。

第一，理论基础构建与问题形式化。 研究首先在量子计算的两个核心模型（门模型与单向量子计算模型）之间建立了桥梁。他们采用了ZX演算这一强大的图形化语言作为统一框架。ZX演算使用“蜘蛛”（spiders，绿色和红色节点）来表示线性映射，并通过一套图重写规则来保证语义等价性。研究详细阐述了如何将测量模式（包括在三个平面上的测量）精确地转换为ZX演算图（称为MBQC形式），反之亦然。这为后续的算法操作提供了严格的数学基础。

第二，推导并形式化保持广义流的图重写规则。 为了开发电路提取算法并对测量模式进行简化，研究者系统性地研究了几种关键的图论操作（局部补、枢轴变换、恒等移除）在ZX演算中的表示，并精确分析了这些操作如何影响测量模式的广义流。这是本研究的一项核心理论贡献。 * 局部补操作与广义流转换：研究者证明了，在一个具有广义流的标记开放图上，对其内部顶点执行局部补操作后，得到的新图仍然具有广义流，并且他们给出了原图的广义流g如何精确转换为新图广义流g'的显式公式。这对于在保持计算确定性的前提下变换资源态至关重要。 * 枢轴操作与恒等移除：类似地，他们证明了在相连的两个顶点上进行枢轴操作（由三次局部补构成）也保持广义流的存在性。更重要的是，他们结合这些操作，展示了如何移除一个具有两个邻居、且测量平面非yz的顶点（即执行“恒等移除”），同时保证剩余的图依然具有广义流。这为后续简化测量模式、减少量子比特数量提供了关键工具。

第三，扩展与聚焦广义流算法。 为了实际地处理和操作广义流，研究者将此前仅适用于xy平面测量的“极大延迟广义流”（maximally delayed gflow）概念和寻找算法，推广到了包含所有三个测量平面的情形。他们提供了一个多项式时间算法，可以判定任意给定标记开放图是否具有扩展广义流，并在存在时输出一个极大延迟的广义流。 此外，他们提出了一种新的“聚焦”（focused）广义流的概念。不同于以往的定义，他们的聚焦性质要求：对于任何非输出顶点v，其校正集g(v)中除v外的所有其他非输出顶点，其测量平面必须为xy；而校正集的奇邻域odd(g(v))中除v外的所有其他非输出顶点，其测量平面必须非xy。他们证明了任何具有广义流的图都存在一个具有此聚焦性质的极大延迟广义流，并给出了构造方法。这种聚焦性质对于后续将测量模式转化为易于提取电路的特殊形式（如相配件形式）非常关键。

第四，开发测量模式简化流程。 利用第二部分推导的图重写规则，研究者展示了一套系统的流程来简化测量模式，核心目标是减少所需测量的量子比特数量，同时保持确定性和计算的语义。 * 移除克利福德顶点：一个关键的简化步骤是移除那些测量在泡利基（即测量角为0或π的倍数，对应于xz或yz平面中的特定角度）的顶点。他们证明，任何测量在xz或yz平面的非输入顶点，都可以从模式中移除，只要同时对图的其余部分和测量指令进行适当的变换。这一过程的正确性严格依赖于之前建立的图重写规则和广义流变换定理。 * 转化为相配件形式：通过结合局部克利福德操作和上述简化规则，研究者展示了如何将任何具有广义流的MBQC+LC形式的ZX图，转化为一种“相配件形式”。在这种形式中，所有非平凡的相位都集中在一些特定的子结构（相配件，phase gadgets）上，而其余部分则由克利福德操作构成。这种形式特别适合于电路提取和优化。

第五，设计并实现电路提取算法。 这是本研究最核心的贡献。研究者提出了一个通用算法，能够从任何具有扩展广义流的测量模式（或其对应的ZX图）中，提取出一个不含辅助比特的等价量子电路。算法的详细工作流程如下： 1. 输入与预处理：算法以一个具有扩展广义流的标记开放图及其测量角作为输入，或等价地，以一个MBQC(+LC)形式的ZX图作为输入。 2. 聚焦广义流与相配件化：算法首先为输入图找到一个聚焦的、极大延迟的广义流。然后，利用第四部分的规则，将对应的ZX图简化为相配件形式。这一步骤显著减少了需要处理的非克利福德操作的数量和复杂性。 3. 迭代提取与电路重建：算法按照广义流定义的偏序（从“最早”测量的顶点开始，逆序处理），迭代地将测量效应和与之关联的校正操作转换为量子门。聚焦广义流的性质确保了在每一步，待处理的顶点v的校正操作只影响xy平面的顶点或输出顶点，这使得转换可以局部地、确定性地进行。具体操作涉及将测量投影表示为受控相位门和泡利校正的组合，并利用ZX演算规则将这些图形结构“拉直”和重排，逐步暴露出标准的量子门（如H, S, T, CNOT, CZ等）。 4. 输出：算法最终输出一个由标准量子门集构成的量子电路，该电路在全局相位因子内等价于原始的测量模式。研究者还提供了一个更实用的算法版本，并附上了伪代码。

主要研究成果与逻辑链条

1. 理论工具突破：研究者成功地将局部补、枢轴等图操作在ZX演算中形式化，并精确刻画了它们对扩展广义流的变换规则。这不仅仅是已知结果的汇编，而是首次系统性地建立了这些变换与广义流保持性之间的严格对应关系，为所有后续的简化与提取操作提供了坚实的理论保障。支持数据/证据：论文中的引理3.1, 3.2, 推论3.3, 引理3.4, 3.12, 3.13等，以及详细的证明过程。
2. 模式简化能力证明：基于上述理论工具，研究者证明了可以安全地移除测量在泡利基的非输入顶点。这一结果具有深刻的物理意义：它表明，对于一个基于测量的计算，所需测量的量子比特数量直接与非克利福德操作的数量相关，因为所有泡利测量都可以被“吸收”到对剩余模式的变换中。支持数据/证据：第四部分“Simplifying measurement patterns”的完整推导，特别是结合了泡利测量转换和克利福德顶点移除规则。
3. 核心算法实现：研究者提出了第一个适用于多平面测量且具有扩展广义流的电路提取算法，并证明了其正确性和高效性。该算法是此前仅适用于xy平面测量算法的非平凡推广。支持数据/证据：第五部分“Circuit extraction”对算法的完整描述，包括一般性描述、更实用的算法步骤、以及与聚焦广义流和相配件形式的结合。附录D提供了算法的伪代码。
4. 通用性扩展：由于算法完全在ZX演算框架内操作，它不仅能处理来源于测量模式的图，实际上可以处理任何满足特定性质（即具有某种广义流类似结构）的ZX图。因此，该算法也是目前已知的最通用的从ZX图提取电路的算法。支持数据/证据：论文明确指出，该算法“not only the most general circuit extraction algorithm for measurement patterns but also the most general known circuit extraction algorithm for ZX-diagrams”。

这些结果之间环环相扣：理论工具（图重写与广义流变换）确保了简化流程的可靠性；简化流程将复杂模式转化为规整形式（相配件形式）；聚焦广义流为规整形式提供了易于处理的局部结构；最终，迭代提取算法利用这种局部结构，逐步构建出最终的量子电路。

研究结论与价值

本研究成功解决了量子计算中一个长期存在的理论问题：如何从允许全平面测量且具有确定性的单向量子计算模型中，高效、无冗余地提取出等价的量子电路。

• 科学价值：
  • 理论统一：深化了对两种主要量子计算模型之间等价关系的理解，特别是在非平凡的多平面测量情形下。
  • 工具创新：提供了一套强大的、基于ZX演算和扩展广义流的数学工具包，用于分析和变换测量模式。
  • 算法完备：填补了算法空白，实现了最通用的电路提取，为相关领域的后续研究奠定了基础。
• 应用价值：
  • 电路优化：本研究形成的完整工作流（电路 → ZX图 → 测量模式 → 简化 → 提取新电路）可直接用于量子电路优化。例如，可以将一个电路转换为测量模式，利用新提出的规则进行简化（减少比特数或深度），再提取回一个可能具有更少T门、更浅深度或更小编译代价的电路。论文图1清晰地描绘了这一优化路径。
  • 验证与编译：该算法为验证单向量子计算程序是否正确实现了预期功能提供了新手段，同时也为将高级算法编译到支持单向量子计算架构的硬件上提供了关键技术。

研究亮点

1. 开创性的算法：这是首个处理扩展广义流（多平面测量）的电路提取算法，具有里程碑意义。
2. 深刻的理论洞见：不仅给出了算法，更深入揭示了图变换、广义流与计算确定性之间的内在联系，特别是关于“泡利测量可移除”的严格证明，深化了人们对测量计算资源消耗的理解。
3. 强大的通用性：借助ZX演算，算法超越了测量模式本身，成为处理更广泛图形化量子计算的通用工具。
4. 系统的构建：研究从基础定义出发，逐步推导理论引理，构建简化流程，最终集成到完整算法中，逻辑严密，体系完整。

其他有价值内容

论文在附录中提供了大量补充材料，包括广义流与确定性关系的详细证明（附录A）、第3部分引理的证明（附录B）、在多平面中寻找极大延迟广义流的算法细节与正确性证明（附录C）以及核心算法的伪代码（附录D）。这些内容为感兴趣的读者和后续研究者验证、复现及扩展本工作提供了极大的便利。