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:2407.17966 · Quantum

Rise of conditionally clean ancillae for efficient quantum circuit constructions

Tanuj Khattar, Craig Gidney

Published May 21, 2025• 16 citations
arXivHTMLPDF

Abstract

We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by \cite{nie2024quantum}, that bridges the gap between traditional clean and dirty ancillae. Like dirty ancillae, they begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation. Like clean ancillae, they can be treated as initialized in a known state within specific computations, thus avoiding the overhead of toggle detection required for dirty ancillae. We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and depths, particularly with limited ancilla availability. Specifically, we provide constructions for:(a) n -controlled NOT using 2 n Toffolis and O ( log ⁡ n ) depth given 2 clean ancillae.(b) n -qubit incrementer using 3 n Toffolis given log 2 ∗ ⁡ n clean ancillae.(c) n -qubit quantum-classical comparator using 3 n Toffolis given log 2 ∗ ⁡ n clean ancillae.(d) unary iteration over [ 0 , N ) using 2.5 N Toffolis given log 2 ∗ ⁡ n clean ancillae.(e) unary iteration via skew tree over [ 0 , N ) using 1.25 N Toffolis given n dirty ancillae.We also introduce laddered toggle detection , a technique to replace clean ancillae with dirty ancillae in all our constructions, incurring a 2x Toffoli gate overhead. Our results demonstrate that conditionally clean ancillae are a valuable tool for quantum circuit design, especially in the resource-constrained early fault-tolerant era.

DOI
10.22331/q-2025-05-21-1752

Related papers

Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla

Abhoy Kole, Majd Assaad, Till Schnittka +1 more

Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.

quant-pharXiv:2605.18169•May 19, 2026•0 citations

Formal Verification of Quantum Ancilla Safety

Jiqi Li, Jingyi Mei, Wang Fang +1 more

Ensuring ancilla safety is a critical correctness requirement for quantum compilation, since ancilla qubits are routinely introduced to implement complex operations with fewer gates and reduced depth. However, formally verifying this property is computationally hard due to state-space explosion in the number of qubits, particularly for dirty ancillae, which carry unknown initial states and must be restored after use. We propose an end-to-end verification-and-repair framework that rigorously addresses both clean and dirty ancilla safety. Our core contribution is a two-step reduction strategy: we first prove that verifying an $m$-qubit dirty ancilla register decomposes into $2m$ independent clean ancilla safety checks; subsequently, we reduce each clean ancilla safety instance to an algebraic commutativity check against Pauli-$Z$ and Pauli-$X$ operators. This approach yields an efficient and naturally parallel verifier and enables actionable diagnosis by classifying violations into logic errors and phase errors. Leveraging this diagnosis, we further design lightweight repair routines that append local single-qubit rotations to eliminate a broad class of local ancilla faults. We implement the full pipeline in a prototype tool using a dual-backend architecture combining decision diagrams and weighted model counting, and validate it on diverse circuits ranging from arithmetic benchmarks to Grover's algorithm. Our experiments demonstrate scalability to thousands of qubits and show that the proposed repairs effectively improve ancilla safety while preserving circuit functionality.

quant-pharXiv:2608.13099•Lecture notes in computer science•Aug 14, 2026•0 citations

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

quant-pharXiv:2603.12917•Mar 16, 2026•0 citations

A Classical-Quantum Adder with Constant Workspace and Linear Gates

Craig Gidney

In 2004, Cuccaro et al found a quantum-quantum adder with $O(n)$ gate cost and $O(1)$ ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and $4n \pm O(1)$ Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of $3n \pm O(1)$ that uses 2 clean ancillae and $n-2$ dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.

arXiv:2507.23079•Jul 30, 2025•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

Quantum circuit for multi-qubit Toffoli gate with optimal resource

Nie, Junhong, Wei Zi, Xiaoming Sun

Resource consumption is an important issue in quantum information processing, particularly during the present NISQ era. In this paper, we investigate resource optimization of implementing multiple controlled operations, which are fundamental building blocks in the field of quantum computing and quantum simulation. We design new quantum circuits for the $n$-Toffoli gate and general multi-controlled unitary, which have only $O(\log n)$-depth and $O(n)$-size, and only require $1$ ancillary qubit. To achieve these results, we explore the potential of ancillary qubits and discover a method to create new conditional clean qubits from existed ancillary qubits. These techniques can also be utilized to construct an efficient quantum circuit for incrementor, leading to an implementation of multi-qubit Toffoli gate with a depth of $O(\log^2n)$ and size of $O(n)$ without any ancillary qubits. Furthermore, we explore the power of ancillary qubits from the perspective of resource theory. We demonstrate that without the assistance of ancillary qubit, any quantum circuit implementation of multi-qubit Toffoli gate must employ exponential precision gates. This finding indicates a significant disparity in computational power of quantum circuits between using and not using ancillary qubits. Additionally, we discuss the comparison of the power of ancillary qubits and extra energy levels in quantum circuit design.

arXiv:2402.05053•Feb 7, 2024•4 citations
We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by \cite{nie2024quantum}, that bridges the gap between traditional clean and dirty ancillae. Like dirty ancillae, they begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation. Like clean ancillae, they can be treated as initialized in a known state within specific computations, thus avoiding the overhead of toggle detection required for dirty ancillae. We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and depths, particularly with limited ancilla availability. Specifically, we provide constructions for:(a) n -controlled NOT using 2 n Toffolis and O ( log ⁡ n ) depth given 2 clean ancillae.(b) n -qubit incrementer using 3 n Toffolis given log 2 ∗ ⁡ n clean ancillae.(c) n -qubit quantum-classical comparator using 3 n Toffolis given log 2 ∗ ⁡ n clean ancillae.(d) unary iteration over [ 0 , N ) using 2.5 N Toffolis given log 2 ∗ ⁡ n clean ancillae.(e) unary iteration via skew tree over [ 0 , N ) using 1.25 N Toffolis given n dirty ancillae.We also introduce laddered toggle detection , a technique to replace clean ancillae with dirty ancillae in all our constructions, incurring a 2x Toffoli gate overhead. Our results demonstrate that conditionally clean ancillae are a valuable tool for quantum circuit design, especially in the resource-constrained early fault-tolerant era.
Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.
Ensuring ancilla safety is a critical correctness requirement for quantum compilation, since ancilla qubits are routinely introduced to implement complex operations with fewer gates and reduced depth. However, formally verifying this property is computationally hard due to state-space explosion in the number of qubits, particularly for dirty ancillae, which carry unknown initial states and must be restored after use. We propose an end-to-end verification-and-repair framework that rigorously addresses both clean and dirty ancilla safety. Our core contribution is a two-step reduction strategy: we first prove that verifying an mmm-qubit dirty ancilla register decomposes into 2m2m2m independent clean ancilla safety checks; subsequently, we reduce each clean ancilla safety instance to an algebraic commutativity check against Pauli-ZZZ and Pauli-XXX operators. This approach yields an efficient and naturally parallel verifier and enables actionable diagnosis by classifying violations into logic errors and phase errors. Leveraging this diagnosis, we further design lightweight repair routines that append local single-qubit rotations to eliminate a broad class of local ancilla faults. We implement the full pipeline in a prototype tool using a dual-backend architecture combining decision diagrams and weighted model counting, and validate it on diverse circuits ranging from arithmetic benchmarks to Grover's algorithm. Our experiments demonstrate scalability to thousands of qubits and show that the proposed repairs effectively improve ancilla safety while preserving circuit functionality.
We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of Θ(n)Θ(n)Θ(n) and depth of Θ(log⁡n)Θ(\log n)Θ(logn) over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from O(n3)\mathcal{O}(n^3)O(n3) to O(n2log⁡2n)\mathcal{O}(n^2 \log^2 n)O(n2log2n) without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.
In 2004, Cuccaro et al found a quantum-quantum adder with O(n)O(n)O(n) gate cost and O(1)O(1)O(1) ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and 4n±O(1)4n \pm O(1)4n±O(1) Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of 3n±O(1)3n \pm O(1)3n±O(1) that uses 2 clean ancillae and n−2n-2n−2 dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
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.
Resource consumption is an important issue in quantum information processing, particularly during the present NISQ era. In this paper, we investigate resource optimization of implementing multiple controlled operations, which are fundamental building blocks in the field of quantum computing and quantum simulation. We design new quantum circuits for the nnn-Toffoli gate and general multi-controlled unitary, which have only O(log⁡n)O(\log n)O(logn)-depth and O(n)O(n)O(n)-size, and only require 111 ancillary qubit. To achieve these results, we explore the potential of ancillary qubits and discover a method to create new conditional clean qubits from existed ancillary qubits. These techniques can also be utilized to construct an efficient quantum circuit for incrementor, leading to an implementation of multi-qubit Toffoli gate with a depth of O(log⁡2n)O(\log^2n)O(log2n) and size of O(n)O(n)O(n) without any ancillary qubits. Furthermore, we explore the power of ancillary qubits from the perspective of resource theory. We demonstrate that without the assistance of ancillary qubit, any quantum circuit implementation of multi-qubit Toffoli gate must employ exponential precision gates. This finding indicates a significant disparity in computational power of quantum circuits between using and not using ancillary qubits. Additionally, we discuss the comparison of the power of ancillary qubits and extra energy levels in quantum circuit design.