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

IEEE/ACM International Symposium on Microarchitecture (MICRO)

Improved Quantum Circuits with Qudits and Dirty Ancillae

Pranav Gokhale, Jonathan M. Baker, Frederic T. Chong

Published Oct 20, 2018• 0 citations
OpenAlex

Related papers

Universality of Hybrid Quantum Gates and Synthesis Without Ancilla Qudits

Guowu Yang, Fei Xie, Xiaoyu Song +1 more

Lecture notes in computer science•Jan 1, 2006•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•1 citation

Efficient quantum circuits for qudits

Gavin K. Brennen, Stephen S. Bullock, Dianne Prost O’Leary

Bulletin of the American Physical Society•Mar 24, 2005•0 citations

Improving ancilla states for quantum computation

Yaakov S. Weinstein, Daniel Chai, Newton Xie

Quantum Information Processing•Jan 9, 2016•4 citations

Rise of conditionally clean ancillae for efficient quantum circuit constructions

Tanuj Khattar, Craig Gidney

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.

arXiv:2407.17966•Quantum•May 21, 2025•51 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•1 citation
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.
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.
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.