MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
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.
Related
- Measurement-Based Uncomputation from an Error Correction Perspective
- Measurement and feedforward circuits from quantum error correcting codes
- Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation
- Exact verification of Givens rotation circuits for efficient quantum phase estimation of iron-sulfur clusters
- Efficient Fidelity Estimation of General Quantum Resource States via Clifford Circuits
BibTeX
@misc{yang2026mbundo,
title = {{MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits}},
author = {Shengyuan Yang and Charles Yuan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02345},
eprint = {2611.02345},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02345},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
AU - Shengyuan Yang
AU - Charles Yuan
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02345
UR - https://arxiv.org/abs/2611.02345
AB - 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.
ER -