Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.02345

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

Shengyuan Yang, Charles Yuan

cs.PLquant-phSubmitted Nov 2, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosedOverclaims
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.

Related papers

Erasynth: Improving Quantum Uncomputation with Structural Measurements

Mingfei Zhang, Anbang Wu, Pu Pang +7 more

In quantum computing, safely clearing temporary ancilla qubits, a process known as uncomputation, is essential to prevent irreversible computational errors caused by entanglement. The typical uncomputation process removes entanglement by reversing gates used to correlate ancilla and (program) data, potentially doubling circuit depth and gate counts. The alternative approach introduces measurements to directly reset ancilla to the ground state and has the potential of reducing uncomputation overhead. Unfortunately, existing measurement-based methods may need to correct the minus sign of exponentially many quantum state terms due to measurement uncertainty, instead incurring larger gate overhead. Our insight to further reduce the uncomputation overhead is to integrate the idea of both methods. To some extent, the unitary-based method is highly structural, reflecting the circuit's computation-uncomputation symmetry, while the measurement-based method introduces randomness due to the uncertainty of the involved qubit set and the resulting phase corrections. Either being too structural or too random introduces high overhead for uncomputation. This work improves existing methods by incorporating structural circuit analysis to suppress the randomness of measurements. This work proposes Erasynth, which analyzes the circuit context and identifies the best timing of applying measurements to release ancilla; unveils the optimal strategy to release ancilla according to the dimension of involved quantum data subspace; prunes and only corrects the key data subspace suffering from measurement-induced phase flip. Experimental evaluations show that Erasynth reduces CX gates by up to 37.48%/97.56% and T gates by up to 50.0%/98.54% over the unitary-based/measurement-based baseline, while also reducing circuit depth by up to 75.62%/98.89%.

International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Nov 4, 2026•0 citations

Optimizing Ancilla-Based Quantum Circuits with SPARE

Ritvik Sharma, Sara Achour

Many quantum algorithms instantiate and use ancillas, spare qubits that serve as temporary storage in a quantum circuit. In particular, many recently developed high-level and modular quantum programming languages (QPLs) use ancilla qubits to implement various programming constructs. These are lowered to circuits with nested/cascading compute-uncompute gate sequences that use ancilla qubits to track internal state. We present SPARE, a rewrite-based quantum circuit optimizer that restructures these compute-uncompute gate sequences, leveraging the ancilla qubit state information to optimize the circuit. In this work, we prove the correctness of SPARE’s rewrites and link SPARE’s gate-level transforms to language-level program rewrites, which may be performed on the input language. We evaluate SPARE on QPL-generated quantum circuits against Unqomp and Spire, two optimizing compilers for QPLs. SPARE achieves a reduction of up to 27.3 % in qubit count, 56.7 % in 2 -qubit gates, 68.2 % in 1-qubit gates and 73.9 % in depth against Unqomp, and up to 17.8 % in qubits, 67.3 % in 2-qubit gates, 61.4 % in 1-qubit gates and 59.9 % in depth against Spire. We also evaluate SPARE against the Quartz, Feynman, and PyZX circuit optimizers: SPARE achieves up to a 70.0 % reduction in two-qubit gates, up to a 53.6 % reduction in 1-qubit gates, and up to a 56.7 % reduction in depth compared to the best result from all the gate-level optimizers.

Proceedings of the ACM on Programming Languages•Jun 10, 2025•9 citations

Measurement-Based Uncomputation from an Error Correction Perspective

Minjun Jeon, Po-Wei Huang, Zhenyu Cai

Coherent uncomputation can be as costly as the computation itself, creating substantial spacetime overheads that can be prohibitive on early fault-tolerant quantum computers. We develop an algebraic framework for measurement-based uncomputation (MBU) through a quantum error-correction picture: measurements of the garbage register induce relative phases analogous to errors causing non-trivial syndromes. Accepting only zero-syndrome outcomes achieves post-selected MBU, removing the need for an uncomputation oracle at the cost of a probabilistic success rate determined by the affine rank of the populated garbage support. This rank can be much smaller than the number of garbage qubits, as illustrated through an example of the HHL algorithm. We then derive a structural condition under which the original uncomputation oracle can be reused to correct the phase for all measurement outcomes. No correction is required for the zero syndrome, while corrections for non-zero syndromes can be further adapted to individual measurement outcomes for simpler circuits, as illustrated by existing modular-arithmetic, QROM, and QRAM MBU constructions. Phase-correction circuits can be further simplified by co-optimising their implementation with the representation of the measurement-induced phases. Selecting which syndrome classes to correct interpolates between post-selected, partially corrected, and deterministic MBU, enabling trade-offs among correction cost, workspace, and repetitions.

quant-pharXiv:2609.31605•Sep 28, 2026•1 citation

Quantum Uncomputation of Clean and Dirty Ancilla Qubits

Chenke Liu, Li Zhou, Boning Meng

Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence checking methods: a syntax-directed static reasoning system and a rewrite-based normalization procedure (\RwUnx), together forming a top-down pipeline. We implement \RwUnx in Qiskit. Compared with the state-of-the-art \Reqompx, \RwUnx handles practical benchmarks with complex dependencies where \Reqompx does not, and achieves higher success rates in random-circuit experiments.

cs.PLCross-listedarXiv:2608.09578•Proceedings of the ACM on Programming Languages•Aug 11, 2026•1 citation

Unqomp: synthesizing uncomputation in Quantum circuits

Anouk Paradis, Benjamin Bichsel, Samuel Steffen +1 more

A key challenge when writing quantum programs is the need for uncomputation: temporary values produced during the computation must be reset to zero before they can be safely discarded. Unfortunately, most existing quantum languages require tedious manual uncomputation, often leading to inefficient and error-prone programs. We present Unqomp, the first procedure to automatically synthesize uncomputation in a given quantum circuit. Unqomp can be readily integrated into popular quantum languages, allowing the programmer to allocate and use temporary values analogously to classical computation, knowing they will be uncomputed by Unqomp. Our evaluation shows that programs leveraging Unqomp are not only shorter (-19% on average), but also generate more efficient circuits (-71% gates and -19% qubits on average).

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)•Jun 18, 2021•43 citations

Exact Unitary Synthesis: Simultaneously Optimal in Size and Depth-Ancilla Tradeoff

Pei Yuan, Wei Zi, Shengyu Zhang

Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget $m\geq 0$ of ancilla, every $n$-qubit unitary can be exactly implemented using a quantum circuit consisting of $O(4^n)$ CNOT and single-qubit gates in $O(n+4^n/(n+m))$ layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.

quant-pharXiv:2610.07010•Oct 6, 2026•1 citation
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 TTT 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%{>}36.5\%>36.5% over uncomputation synthesizers.
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 ∣0⟩\ket{0}∣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-XXX gate of a lifetime; interval MBU measures after the ancilla’s last use and replaces subsequent controlled-XXX writes with in-place, measurement-conditioned phase corrections. Soundness is proved under the final-zero promise. Analysis takes expected O(N2)O(N^2)O(N2) time in circuit-description size; transformation takes O(N)O(N)O(N) time. Under a stated gate-decomposition assumption, neither transformation increases TTT count for any measurement outcome.
Across 22 benchmarks, endpoint and interval MBU reduce geometric-mean TTT counts relative to Reqomp by 36.5% and 40.0%, respectively, including relative-phase-Toffoli post-processing. Interval MBU matches the TTT-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 TTT-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.
In quantum computing, safely clearing temporary ancilla qubits, a process known as uncomputation, is essential to prevent irreversible computational errors caused by entanglement. The typical uncomputation process removes entanglement by reversing gates used to correlate ancilla and (program) data, potentially doubling circuit depth and gate counts. The alternative approach introduces measurements to directly reset ancilla to the ground state and has the potential of reducing uncomputation overhead. Unfortunately, existing measurement-based methods may need to correct the minus sign of exponentially many quantum state terms due to measurement uncertainty, instead incurring larger gate overhead. Our insight to further reduce the uncomputation overhead is to integrate the idea of both methods. To some extent, the unitary-based method is highly structural, reflecting the circuit's computation-uncomputation symmetry, while the measurement-based method introduces randomness due to the uncertainty of the involved qubit set and the resulting phase corrections. Either being too structural or too random introduces high overhead for uncomputation. This work improves existing methods by incorporating structural circuit analysis to suppress the randomness of measurements. This work proposes Erasynth, which analyzes the circuit context and identifies the best timing of applying measurements to release ancilla; unveils the optimal strategy to release ancilla according to the dimension of involved quantum data subspace; prunes and only corrects the key data subspace suffering from measurement-induced phase flip. Experimental evaluations show that Erasynth reduces CX gates by up to 37.48%/97.56% and T gates by up to 50.0%/98.54% over the unitary-based/measurement-based baseline, while also reducing circuit depth by up to 75.62%/98.89%.
Many quantum algorithms instantiate and use ancillas, spare qubits that serve as temporary storage in a quantum circuit. In particular, many recently developed high-level and modular quantum programming languages (QPLs) use ancilla qubits to implement various programming constructs. These are lowered to circuits with nested/cascading compute-uncompute gate sequences that use ancilla qubits to track internal state. We present SPARE, a rewrite-based quantum circuit optimizer that restructures these compute-uncompute gate sequences, leveraging the ancilla qubit state information to optimize the circuit. In this work, we prove the correctness of SPARE’s rewrites and link SPARE’s gate-level transforms to language-level program rewrites, which may be performed on the input language. We evaluate SPARE on QPL-generated quantum circuits against Unqomp and Spire, two optimizing compilers for QPLs. SPARE achieves a reduction of up to 27.3 % in qubit count, 56.7 % in 2 -qubit gates, 68.2 % in 1-qubit gates and 73.9 % in depth against Unqomp, and up to 17.8 % in qubits, 67.3 % in 2-qubit gates, 61.4 % in 1-qubit gates and 59.9 % in depth against Spire. We also evaluate SPARE against the Quartz, Feynman, and PyZX circuit optimizers: SPARE achieves up to a 70.0 % reduction in two-qubit gates, up to a 53.6 % reduction in 1-qubit gates, and up to a 56.7 % reduction in depth compared to the best result from all the gate-level optimizers.
Coherent uncomputation can be as costly as the computation itself, creating substantial spacetime overheads that can be prohibitive on early fault-tolerant quantum computers. We develop an algebraic framework for measurement-based uncomputation (MBU) through a quantum error-correction picture: measurements of the garbage register induce relative phases analogous to errors causing non-trivial syndromes. Accepting only zero-syndrome outcomes achieves post-selected MBU, removing the need for an uncomputation oracle at the cost of a probabilistic success rate determined by the affine rank of the populated garbage support. This rank can be much smaller than the number of garbage qubits, as illustrated through an example of the HHL algorithm. We then derive a structural condition under which the original uncomputation oracle can be reused to correct the phase for all measurement outcomes. No correction is required for the zero syndrome, while corrections for non-zero syndromes can be further adapted to individual measurement outcomes for simpler circuits, as illustrated by existing modular-arithmetic, QROM, and QRAM MBU constructions. Phase-correction circuits can be further simplified by co-optimising their implementation with the representation of the measurement-induced phases. Selecting which syndrome classes to correct interpolates between post-selected, partially corrected, and deterministic MBU, enabling trade-offs among correction cost, workspace, and repetitions.
Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence checking methods: a syntax-directed static reasoning system and a rewrite-based normalization procedure (\RwUnx), together forming a top-down pipeline. We implement \RwUnx in Qiskit. Compared with the state-of-the-art \Reqompx, \RwUnx handles practical benchmarks with complex dependencies where \Reqompx does not, and achieves higher success rates in random-circuit experiments.
A key challenge when writing quantum programs is the need for uncomputation: temporary values produced during the computation must be reset to zero before they can be safely discarded. Unfortunately, most existing quantum languages require tedious manual uncomputation, often leading to inefficient and error-prone programs. We present Unqomp, the first procedure to automatically synthesize uncomputation in a given quantum circuit. Unqomp can be readily integrated into popular quantum languages, allowing the programmer to allocate and use temporary values analogously to classical computation, knowing they will be uncomputed by Unqomp. Our evaluation shows that programs leveraging Unqomp are not only shorter (-19% on average), but also generate more efficient circuits (-71% gates and -19% qubits on average).
Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget m≥0m\geq 0m≥0 of ancilla, every nnn-qubit unitary can be exactly implemented using a quantum circuit consisting of O(4n)O(4^n)O(4n) CNOT and single-qubit gates in O(n+4n/(n+m))O(n+4^n/(n+m))O(n+4n/(n+m)) layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.