Rise of conditionally clean ancillae for efficient quantum circuit constructions

Abstract

We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by [NZS24], 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 $2n$ Toffolis and $O(\log n)$ depth given 2 clean ancillae. (b) $n$-qubit incrementer using $3n$ Toffolis given ${\log }_2^{\ast }n$ clean ancillae. (c) $n$-qubit quantum-classical comparator using $3n$ Toffolis given ${\log }_2^{\ast }n$ clean ancillae. (d) unary iteration over $[0,N)$ using $2.5N$ Toffolis given ${\log }_2^{\ast }n$ clean ancillae. (e) unary iteration via skew tree over $[0,N)$ using $1.25N$ 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.

References in corpus (6)

• Surface codes: Towards practical large-scale quantum computation
• Novel constructions for the fault-tolerant Toffoli gate
• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
• Expressing and Analyzing Quantum Algorithms with Qualtran
• Quantum circuit for multi-qubit Toffoli gate with optimal resource
• Quantifying fault tolerant simulation of strongly correlated systems using the Fermi-Hubbard model

Cited by in corpus (7)

• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Fault-tolerant quantum simulation of generalized Hubbard models
• Quantum state preparation via piecewise QSVT
• Transversal AND in Quantum Codes
• Benincasa-Dowker-Glaser causal set actions by quantum counting
• Efficient implementation of single particle Hamiltonians in exponentially reduced qubit space
• Quantum Circuits Are Just a Phase