⚛️ 量子物理

MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits

本文介绍了 MBUndo，这是一种利用静态分析将具有标准幺正反计算（unitary uncomputation）的任意量子线路安全地转换为更高效的基于测量的反计算（measurement-based uncomputation）的自动编译器通道，在除了辅助比特识别之外无需用户额外标注的情况下，实现了超过 36.5% 的昂贵 T 门减少。

原作者： Shengyuan Yang, Charles Yuan

发布于 2026-11-03

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Shengyuan Yang, Charles Yuan

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

量子计算机有望解决当今机器需要数千年才能破解的问题，从设计新药到模拟复杂的气候系统。但这些机器极其脆弱。为了工作，它们必须将信息保持在一种微妙的叠加态，即粒子同时存在于多种可能性之中。如果一个粒子与外界发生相互作用或失去了与其余系统的连接，该信息就会坍缩，导致计算失败。这种危险的一个主要来源来自于计算机自身的内部过程。当运行量子程序时，它经常会创建临时的辅助粒子，称为辅助比特（ancillas），用于存储中间结果。一旦对辅助比特的使用完成，它不能简单地被丢弃。因为这些辅助比特与主要数据粒子深度耦合，丢弃它们会扰乱整个计算结果。相反，计算机必须仔细地逆转用于创建辅助比特的步骤，使其返回到一个中性状态而不干扰数据。这个被称为“反向计算”（uncomputation）的过程对于保证正确性至关重要，但也是昂贵的，消耗了计算机有限资源中的很大一部分。

多年来，执行这种清理的标准方法是运行完全相同的逻辑门并进行反向操作，实际上是在为辅助比特倒转时钟。然而，一种更高效的方法出现了，它用简单的观察取代了这种缓慢、机械的反向过程。通过测量辅助比特，计算机可以迫使它重置，前提是如果测量结果产生特定结果，计算机需对主要数据应用一个快速且廉价的修正。这种被称为“基于测量的反向计算”（measurement-based uncomputation）的技术成本远低于传统方法，但一直难以实现自动化使用。直到现在，研究人员必须手动识别在电路中的何处可以使用这一技巧，并手动重写代码，这项繁琐的任务限制了其仅能用于最简单的设计。一个名为 MBUndo 的新工具改变了这一点，它能够自动扫描任何量子电路，寻找每一个可以将昂贵的回转操作替换为廉价测量的机会，并重写代码以使其生效。

开发 MBUndo 的研究人员——来自威斯康星大学麦迪逊分校的 Shengyuan Yang 和 Charles Yuan——面临着两个阻碍了过去自动化的基本障碍。首先，他们需要准确知道在复杂电路中的哪个位置，辅助比特已经准备好进行测量。在一个长程序中，一根物理导线可能会被多次复用，以持有不同的临时值，每个值都有自己的起始和结束时间。寻找一个辅助比特不再需要但仍可安全测量的精确时刻，需要一种看待电路流向的新方法。其次，他们需要弄清楚如何用一个简单的测量和一个修正来替换一系列复杂的逻辑门，而不破坏计算。之前的尝试之所以失败，是因为它们将一组逻辑门视为不可更改的块，这往往会导致错误或错失节省机会。

为了解决第一个问题，团队开发了一种方法，通过从程序的末尾开始向后追踪每一个辅助比特的生命周期。他们不将每个粒子的值视为一个固定的数字，而是将其视为它所持有的数据的符号表达式。通过向后遍历电路，他们可以确定辅助比特的值何时回归为零，从而标记其有用寿命的终点。这种分析表明，许多电路中隐藏着多个辅助比特可以被测量的时刻，远比人类设计师能发现的要多。针对第二个挑战，他们创建了两种不同的策略。第一种被称为“端点测量”（endpoint measurement），它简单地将使用辅助比特的最后一个逻辑门替换为测量和修正。第二种更高级的策略被称为“区间测量”（interval measurement），它观察用于清理辅助比特的一整串逻辑门序列。它将这个序列拆解，用一系列取决于测量结果的廉ales修正来替换昂贵的逻辑门。这使得计算机可以完全跳过反转逻辑门的沉重工作，只要测量结果是理想的。

该团队将 MBUndo 构建为一个编译器传递（compiler pass），这是一个位于量子程序员和硬件之间的工具。它接收一个已经使用标准、昂贵清理方法的电路，并自动将其转换为使用更便宜的基于测量的反向计算方法。该工具除了识别哪些导线是辅助比特之外，不需要用户提供任何特殊输入，而这正是现有工具也需要的信息。在对二十二个不同的基准电路（涵盖从简单算术到复杂加密算法）进行测试时，MBUndo 表现得非常出色。与现有的最佳自动化方法相比，它平均减少了超过 36.5% 的最昂贵类型的门（即 T 门）。在清理过程涉及长链逻辑门的情况下，节省效果更为显著，将成本降低了近一半。该工具的表现还匹配或超越了由专家针对特定任务进行手动优化的电路，且在标准笔记本电脑上仅需不到一秒即可完成。

这项工作的意义在于它能让强大的优化技术面向所有人，而不仅仅是电路专家。通过将基于测量的反向计算自动化，MBUndo 移除了在未来硬件上运行复杂量子算法的主要障碍。研究人员证明了他们的方法是可靠的，这意味着它绝不会产生错误答案；同时也是高效的，意味着它能持续降低资源成本。虽然目前的量子计算机规模仍然较小，但通往实用化机器的路径需要最小化每一项可能的成本。通过展示可以通过自动转换来消除很大一部分计算开销，这项工作为更实际、更强大的量子计算提供了一条清晰的路径。其结果表明，量子软件的未来将不再依赖于人工的逐个逻辑门调优，而是更多地依赖于能够发现并自动应用这些效率增益的智能编译器。

技术摘要：MBUndo

问题陈述

量子程序经常利用存储在辅助比特（ancilla qubits）中的临时值。为了确保计算的正确性，必须将这些辅助比特恢复到 $|0\rangle$ 态，这一过程被称为逆向计算（uncomputation），旨在将它们与数据比特解纠缠。传统上，这通过**酉逆向计算（unitary uncomputation）**来实现，即执行计算电路的逆过程，仅使用酉门。这种方法成本高昂，往往占据了高达一半的运行时间，并且需要大量的非 Clifford $T$ 门，而 $T$ 门是容错量子计算中的主要瓶颈。

**基于测量的逆向计算（Measurement-Based Uncomputation, MBU）**提供了一种更廉价的替代方案，它通过测量和条件相位修正来取代昂贵的酉门。虽然 MBU 已被成功手动应用于特定的电路设计（例如 Toffoli 门或特定的加法器），并在某些框架中被推广到单门原语，但目前尚不存在能够自动将任意量子电路（由标准酉逆向计算合成器生成）转换为 MBU 的自动转换工具。该领域对于两个基本问题缺乏答案：(1) 在一个复杂的、重复使用辅助比特的电路中，Mбе 在何处可以安全适用？(2) 如何将多门逆向计算序列转化为高效的相位修正，而不损害其正确性和效率？

方法论

作者提出了 MBUndo，这是一个编译器传递（compiler pass），能够自动将任意量子电路从酉逆向计算转换为基于测量的逆向计算。该方法由三个核心组件组成：

1. 辅助比特寿命的静态分析

为了确定 MBU 的适用位置，MBUndo 采用了**反向符号执行（backward symbolic execution）**分析。

符号表示： 该分析并不追踪完整的量子态（这会导致指数级爆炸），而是将每个比特的值追踪为一个符号值：一组由异或（ $\oplus$ ）连接的原子（atoms）。原子要么是未知基底值的符号，要么是值的乘积。这种表示法比代数正规型（ANF）更紧凑，并避免了分配律展开，确保原子数量相对于电路规模呈线性增长。
反向执行： 从电路末尾（此时辅助比特保证为 $|0\rangle$ $∣0 ⟩$ ）开始，分析按反向顺序处理门：
- XOR 门（如 CNOT, Toffoli）： 将控制值的乘积异或到目标值中。
- 对角门（如 $Z, S, T$ ）： 保持值不变。
- 基底变换门（如 $H$ ）： 保守地将目标替换为一个新的符号。
寿命识别： 分析识别出辅助比特的符号值为空集（代表 0）的“零点”。这些点划定了辅助比特在物理导线上不同的逻辑寿命（logical lifetimes），即使在单个导线被用于处理不同临时值的情况下，也能揭示多次进行 MBU 的机会。

2. 电路变换

基于识别出的寿命，MBUndo 应用了两种可靠的变换：

端点 MBU（Endpoint MBU）： 这种变换自动实现了 Gidney 规则，适用于每个辅助比特寿命的最后一个门。如果最后一个逆向计算门是受控 $X$ 门（C $^k$ X），则将其替换为 $X$ 基底测量以及随后的条件相位修正（C $^{k-1}$ Z）。通过消除对逆向酉操作的需求，这减少了 $T$ 门的计数，前提是修正操作更廉价（对于 Clifford 门而言确实如此）。
区间 MBU（Interval MBU）： 这种高级变换处理辅助比特寿命内的门序列。它识别辅助比特的“最后一次使用”（即作为控制位或被非 XOR 门修改时）并定义了一个由后续 XOR 门组成的“区间”，这些门负责将辅助比特恢复为零。
- 辅助比特在最后一次使用后立即进行测量。
- 区间内的每个 XOR 门都被替换为一个基于测量结果的经典控制相位修正（ $Z$ 旋转）。
- 这种方法通过隔离辅助比特的寿命并确保相位修正的应用既可靠又高效，避免了先前研究中的“整体式（monolithic）”缺陷（即先前研究将逆向计算块视为不透明的整体，当数据比特被修改时会产生不安全性）。

3. 实现

MBUndo 实现为 Qiskit 2.5.2 之上的一个编译器传递。它接收一个电路和一组辅助比特列表，执行静态分析，应用变换，并输出带有基于测量的逆向计算的电路。它还包括预处理和后处理步骤，以处理相对相位 Toffoli (RCCX) 门，从而确保与 Unqomp 和 Reqomp 等现有合成器的兼容性。

核心贡献

静态分析： 一种可靠且高效的反向符号执行算法，能够识别任意电路中辅助比特的多个逻辑寿命，在无需用户除辅助比特识别外进行额外标注的情况下，最大化 MBU 的应用机会。
端点 MBU： 一种能够可靠地自动实现 Gidney 规则以处理每个辅助比特寿命最后一个门的变换。
区间 MBU： 一种新型变换，能够将多门酉逆向计算序列可靠地转换为高效的相位修正序列，推广了以往仅限于单门或特定结构的规则。
MBUndo 工具： 一个集成编译器传递，能够自动增强现有逆向计算合成器的输出。
实证评估： 通过 22 个基准测试进行了全面评估，展示了显著的 $T$ 门削减。

结果

作者在 22 个基准测试（包括来自逆向计算合成器 Reqomp, Unqomp, RwUn 以及手动设计的 MBU 电路）上对 MBUndo 进行了评估。

$T$ 门削减： 与最先进的合成器 Reqomp 相比，MBUndo 的 Endpoint MBU 在经过后处理后，使 $T$ 门计数减少了 36.5%（几何平均值）。更高级的 Interval MBU 在包含后处理的完整 22 个基准测试集中，相对于 Reqomp 实现了 40.0% 的削减。对于包含多门逆向计算的基准测试，Interval MBU 相比 Endpoint MBU 提供了 2.3% 至 18.4% 的额外削减。
与手动设计对比： MBUndo 能够自动匹配或超过针对特定算法（如 GidneyAdder, QLZOC）的手动构建 MBU 电路的效率，在无需人工干预的情况下重现了其 $T$ 门节省效果。
与整体式 MBU 对比： MBUndo 显著优于“整体式 MBU”（Luongo 等人）方法，后者在一般情况下被证明是不安全的，且在某些情况下效率低下。在不进行后处理的情况下，MBUndo 比最佳整体式 MBU 性能（23.1%）减少了 47.9% 的 $T$ 门。
可扩展性： MBUndo 在不到 43 毫秒 内即可处理完所有 22 个基准测试。即使对于大型电路（如 400 位加法器），其运行时间也保持在 0.1 秒以下，而上游合成器（Reqomp）则需要数分钟。
与优化器对比： 在大多数基准测试中，即使将 Tzap 和 SPARE 等通用优化器应用于酉输出，MBUndo 也能比它们更有效地减少 $T$ 门计数。

重要性

本文声称 MBUndo 开启了自动且系统地将量子电路转换为使用基于测量的逆向计算的研究。其重要性在于：

降低门槛： 它将 MBU 的性能优势——此前仅能通过专家设计的手动优化获得——带给了一大类由标准编译器生成的量子程序。
增强合成能力： 它作为现有逆向计算合成器的补充层，在无需修改合成算法本身的情况下增强了其输出。
赋能动态电路： 通过成功地将酉电路自动转换为涉及测量和经典前馈的动态电路，它推动了动态量子电路编译器技术的发展，有望解锁单纯依靠酉优化无法实现的成本降低。

该工作范围适中，专注于针对容错架构的 $T$ 门削减，并承认未来的工作可以纳入更细粒度的架构成本模型和语言级自动化。