arXiv:2611.02345
MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
Shengyuan Yang, Charles Yuan
Abstract
Quantum programs that use temporary values, known as \emph{ancilla} qubits, must explicitly \emph{uncompute} each ancilla back to zero to ensure that the program produces correct outputs. Conventional uncomputation uses unitary quantum gates, whereas leading quantum algorithms now leverage \emph{measurement-based uncomputation} (MBU), which replaces costly unitary $T$ gates with cheaper measurements and phase corrections. Current quantum programming frameworks can use measurement to uncompute specific gates such as Toffoli. No automatic transformation, however, accepts an arbitrary circuit whose ancillas are computed and uncomputed via the standard approach and converts the circuit to use MBU\@. Researchers instead apply MBU to individual circuit designs by hand, which limits algorithm development and compiler optimization. Such a transformation has not existed due to two fundamental unknowns: where MBU applies and which gates realize MBU for an arbitrary computation. To solve these, we first present a static analysis that identifies, for each ancilla qubit, each circuit position where measurement is sound --- subsuming basic assumptions that MBU only applies at the end of a circuit. Next, we present circuit transformations that soundly turn unitary uncomputation gates into efficient phase corrections after measurement --- generalizing rewrite rules from prior literature that are either limited to a single gate or not applicable to a general circuit. We present \textsf{MBUndo}, an integrated compiler pass that automatically converts circuits to measurement-based uncomputation. It requires no user annotations other than which qubits are ancillas, the same as needed by existing uncomputation synthesizers, and can enhance their output circuits. We evaluate \textsf{MBUndo} on 22 benchmarks to reveal \emph{T} gate reductions of ${>}36.5\%$ over uncomputation synthesizers.
AI Summary
Measurement-based uncomputation (MBU) can replace ancilla-cleanup gates with measurements and conditional phase corrections, but existing implementations largely require gate-specific primitives or manually designed circuits. This paper addresses automatic conversion of circuits containing unitary uncomputation into circuits using MBU, requiring only identification of ancillas promised to finish in $\ket{0}$. MBUndo combines backward symbolic execution with two transformations. The analysis conservatively identifies zero points and logical lifetimes on reused ancilla wires, using compact Boolean expressions rather than fully expanded algebraic normal forms. Endpoint MBU replaces the final controlled-$X$ gate of a lifetime; interval MBU measures after the ancilla’s last use and replaces subsequent controlled-$X$ writes with in-place, measurement-conditioned phase corrections. Soundness is proved under the final-zero promise. Analysis takes expected $O(N^2)$ time in circuit-description size; transformation takes $O(N)$ time. Under a stated gate-decomposition assumption, neither transformation increases $T$ count for any measurement outcome. Across 22 benchmarks, endpoint and interval MBU reduce geometric-mean $T$ counts relative to Reqomp by 36.5% and 40.0%, respectively, including relative-phase-Toffoli post-processing. Interval MBU matches the $T$-count savings of three of four evaluated published MBU constructions, but not specialized table lookup. Compilation takes at most 43 ms on these benchmarks and one second in larger scaling tests. The analysis can miss opportunities because its symbolic representation is conservative. The implementation operates at circuit level, and its primarily $T$-count-based evaluation does not model architecture-specific measurement, decoding, or feed-forward costs; language-level automation and architecture-aware costing are identified as future directions.
The authors used Claude Fable 5.1 by Anthropic to implement the algorithms, to write tests for the implementation and evaluation, and to write scripts for running the experiments.
Error found: The abstract overstates the completeness of lifetime analysis by claiming to identify each sound measurement position, whereas the analysis is explicitly conservative and can miss valid zero points.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.