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 Architectural Support for Programming Languages and Operating Systems (ASPLOS)

Borrowing Dirty Qubits in Quantum Programs

Bonan Su, Li Zhou, Yuan Feng, Mingsheng Ying

Published Mar 10, 2026• 1 citation
Publisher

Abstract

Dirty qubits are ancillary qubits that can be borrowed from idle parts of a computation, enabling qubit reuse and reducing the demand for fresh, clean qubits---a resource that is typically scarce in practice. For such reuse to be valid, the initial states of the dirty qubits must not affect the functionality of the quantum circuits in which they are employed. Moreover, their original states, including any entanglement they possess, must be fully restored after use---a requirement commonly known as safe uncomputation.

DOI
10.1145/3779212.3790134

Related papers

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

Bona: Automatic Management of Dirty Ancilla Borrowing in Quantum Circuits

Xiaoquan Xu, Chenke Liu, Boning Meng +2 more

The management of ancilla qubits has become a critical technique for reducing quantum circuit width. Dirty ancillas, which may be borrowed from any temporarily idle qubit regardless of their initial states, offer substantial flexibility for width optimization, but their use has so far required manual and error-prone handling. We formalize the dirty-qubit borrowing problem and establish a fundamental computational limit by proving its NP-hardness. To support practical optimization, we present \bona, the first scheduler for dirty-qubit borrowing, built on a novel depth-aware heuristic algorithm. We evaluate \bona~ across a variety of benchmarks, including practical quantum circuits and randomly arranged compositions of real circuit modules, and find that it reduces nearly 99\% of dirty ancillas on average with controlled depth overhead. In particular, for parallel quantum walk---an essential component of parallel Hamiltonian simulation---\bona~ matches the circuit width achieved by the clean-qubit schemes of \citeauthor{jiang2024recycling}~(\citeyear{jiang2024recycling}) and \citeauthor{quantinuum}~(\citeyear{quantinuum}), but attains significantly smaller circuit depth, providing concrete evidence that dirty ancillas offer unique optimization advantages in circuits with certain parallelism.

cs.PLCross-listedarXiv:2608.08765•Aug 11, 2026•0 citations

Uncomputing Ancilla Qubits in Quantum Circuits

Ashutosh Tiwari, Ranjani G. Sundaram, Himanshu Gupta +2 more

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.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 31, 2025•2 citations

Optimal Dependency-Aware Qubit Reuse for Scheduled Quantum Circuits

Pin-Wen Liu, Kai-Xu Zhan, Jian-Jhih Kuo

Quantum computing is widely regarded as a promising technology due to its potential to offer exponential computational advantages over classical systems. However, practical deployment and realization of most quantum algorithms remain constrained by the limitations of current quantum architectures– most notably, the limited number of physical qubits available in quantum processing units (QPUs). Therefore, efficient utilization of quantum resources has become a crucial concern in the field. Thus, in this paper, we explore the nature of qubit reuse. Based on our findings, we formulate an optimization problem and propose a novel algorithm to minimize the number of qubits for scheduled quantum circuits. Finally, extensive simulation results on various practical benchmarks manifest that our algorithm can significantly outperform the existing approach in qubit reuse.

Globecom•Dec 8, 2025•0 citations

Fast Cliffords When Your Quantum Memory Is Full

Marten Folkertsma, Ian Mertz, Sergii Strelchuk +1 more

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.

quant-pharXiv:2609.40144•Oct 1, 2026•0 citations

Quantum computation with superconductors

Amaia Irastorza Gabilondo

Quantum computation using supercoducting qubits. Qubits are quantum bits used in quantum computers. Superconducting qubits are a strong option for building a quantum computer. But not just that, as they are macroscopic objects they question the limits of quantum physics.

•Jan 10, 2017•1 citation
Dirty qubits are ancillary qubits that can be borrowed from idle parts of a computation, enabling qubit reuse and reducing the demand for fresh, clean qubits---a resource that is typically scarce in practice. For such reuse to be valid, the initial states of the dirty qubits must not affect the functionality of the quantum circuits in which they are employed. Moreover, their original states, including any entanglement they possess, must be fully restored after use---a requirement commonly known as safe uncomputation.
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.
The management of ancilla qubits has become a critical technique for reducing quantum circuit width. Dirty ancillas, which may be borrowed from any temporarily idle qubit regardless of their initial states, offer substantial flexibility for width optimization, but their use has so far required manual and error-prone handling. We formalize the dirty-qubit borrowing problem and establish a fundamental computational limit by proving its NP-hardness. To support practical optimization, we present \bona, the first scheduler for dirty-qubit borrowing, built on a novel depth-aware heuristic algorithm. We evaluate \bona~ across a variety of benchmarks, including practical quantum circuits and randomly arranged compositions of real circuit modules, and find that it reduces nearly 99\% of dirty ancillas on average with controlled depth overhead. In particular, for parallel quantum walk---an essential component of parallel Hamiltonian simulation---\bona~ matches the circuit width achieved by the clean-qubit schemes of \citeauthor{jiang2024recycling}~(\citeyear{jiang2024recycling}) and \citeauthor{quantinuum}~(\citeyear{quantinuum}), but attains significantly smaller circuit depth, providing concrete evidence that dirty ancillas offer unique optimization advantages in circuits with certain parallelism.
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.
Quantum computing is widely regarded as a promising technology due to its potential to offer exponential computational advantages over classical systems. However, practical deployment and realization of most quantum algorithms remain constrained by the limitations of current quantum architectures– most notably, the limited number of physical qubits available in quantum processing units (QPUs). Therefore, efficient utilization of quantum resources has become a crucial concern in the field. Thus, in this paper, we explore the nature of qubit reuse. Based on our findings, we formulate an optimization problem and propose a novel algorithm to minimize the number of qubits for scheduled quantum circuits. Finally, extensive simulation results on various practical benchmarks manifest that our algorithm can significantly outperform the existing approach in qubit reuse.
Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every nnn-qubit Clifford circuit has a catalytic implementation of depth O(log⁡n)O(\log n)O(logn) using O(n2/log⁡2n)O(n^2/\log^2 n)O(n2/log2n) catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level CkC_kCk​ of the Clifford hierarchy, which admit catalytic implementations of depth O(log⁡(n+1))O(\log(n+1))O(log(n+1)) with O(nk/log⁡(n))O(n^k/\log(n))O(nk/log(n)) gates and O(nk/log⁡2(n))O(n^k/\log^2(n))O(nk/log2(n)) catalytic qubits, as well as to semi-Clifford Gates.