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

International Conference on Quantum Communications, Networking, and Computing (QCNC)

Uncomputing Ancilla Qubits in Quantum Circuits

Ashutosh Tiwari, Ranjani G. Sundaram, Himanshu Gupta, C. R. Ramakrishnan, Nengkun Yu

Published Mar 31, 2025• 3 citations
Publisher

Abstract

Uncomputation of ancilla qubits is essential in quantum computing to reset auxiliary qubits to a zero state, ensuring their safe discarding and reducing resource overhead. Current methods for uncomputation either rely on manual procedures or use additional ancilla qubits to store intermediate computation results, which increases qubit storage requirements. Additionally, most in-place uncomputation techniques employ an all-or-nothing strategy, wherein they perform uncomputation only when all ancilla qubits in the given circuit can be uncomputed.In this work, we tackle the problem of uncomputing a maximum number of ancilla qubits in a quantum circuit with minimal qubit storage overhead. We propose a novel approach where partial uncomputation—reverting the last ’m’ gates—enables the uncomputation of more qubits. We present three algorithms designed to uncompute the largest possible set of ancilla qubits and demonstrate their effectiveness through experiments on various randomly generated quantum circuits.

DOI
10.1109/qcnc64685.2025.00065

Related papers

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

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

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

Shengyuan Yang, Charles Yuan

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.

cs.PLCross-listedarXiv:2611.02345•Nov 3, 2026•0 citations

Efficient Quantum Circuit Decompositions via Intermediate Qudits

Jonathan M. Baker, Casey Duckering, Frederic T. Chong

Many quantum algorithms make use of ancilla, additional qubits used to store temporary information during computation, to reduce the total execution time. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial. In this work, we give a method to generate ancilia out of idle qubits by placing some in higher-value states, called qudits. We show how to take a circuit with many O(n) ancilla and design an ancilla-free circuit with the same asymptotic depth. Using this, we give a circuit construction for an in-place adder and a constant adder both with O(log n) depth using temporary qudits and no ancilla.

arXiv:2002.10592•IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Nov 1, 2020•28 citations

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

Reqomp: Space-constrained Uncomputation for Quantum Circuits

Anouk Paradis, Benjamin Bichsel, Martin Vechev

Quantum circuits must run on quantum computers with tight limits on qubit and gate counts. To generate circuits respecting both limits, a promising opportunity is exploiting uncomputation to trade qubits for gates. We present Reqomp, a method to automatically synthesize correct and efficient uncomputation of ancillae while respecting hardware constraints. For a given circuit, Reqomp can offer a wide range of trade-offs between tightly constraining qubit count or gate count. Our evaluation demonstrates that Reqomp can significantly reduce the number of required ancilla qubits by up to 96%. On 80% of our benchmarks, the ancilla qubits required can be reduced by at least 25% while never incurring a gate count increase beyond 28%.

arXiv:2212.10395•Quantum•Feb 19, 2024•18 citations
Uncomputation of ancilla qubits is essential in quantum computing to reset auxiliary qubits to a zero state, ensuring their safe discarding and reducing resource overhead. Current methods for uncomputation either rely on manual procedures or use additional ancilla qubits to store intermediate computation results, which increases qubit storage requirements. Additionally, most in-place uncomputation techniques employ an all-or-nothing strategy, wherein they perform uncomputation only when all ancilla qubits in the given circuit can be uncomputed.In this work, we tackle the problem of uncomputing a maximum number of ancilla qubits in a quantum circuit with minimal qubit storage overhead. We propose a novel approach where partial uncomputation—reverting the last ’m’ gates—enables the uncomputation of more qubits. We present three algorithms designed to uncompute the largest possible set of ancilla qubits and demonstrate their effectiveness through experiments on various randomly generated quantum circuits.
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).
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%.
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.
Many quantum algorithms make use of ancilla, additional qubits used to store temporary information during computation, to reduce the total execution time. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial. In this work, we give a method to generate ancilia out of idle qubits by placing some in higher-value states, called qudits. We show how to take a circuit with many O(n) ancilla and design an ancilla-free circuit with the same asymptotic depth. Using this, we give a circuit construction for an in-place adder and a constant adder both with O(log n) depth using temporary qudits and no ancilla.
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.
Quantum circuits must run on quantum computers with tight limits on qubit and gate counts. To generate circuits respecting both limits, a promising opportunity is exploiting uncomputation to trade qubits for gates. We present Reqomp, a method to automatically synthesize correct and efficient uncomputation of ancillae while respecting hardware constraints. For a given circuit, Reqomp can offer a wide range of trade-offs between tightly constraining qubit count or gate count. Our evaluation demonstrates that Reqomp can significantly reduce the number of required ancilla qubits by up to 96%. On 80% of our benchmarks, the ancilla qubits required can be reduced by at least 25% while never incurring a gate count increase beyond 28%.