© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal 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• 2 citations

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•34 citations

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%.

Quantum•Feb 19, 2024•9 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•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•19 citations

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•Dec 20, 2022•0 citations

Decomposition of Multi-Qubit Gates for Circuit Cutting

Ryota Tamura, Tomoya Kashimata, Yohei Hamakawa +2 more

A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.

quant-pharXiv:2603.26278•Mar 30, 2026•0 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).

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%.

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.

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.

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%.

A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.