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 (17)

• Surface codes: Towards practical large-scale quantum computation
• Toward the first quantum simulation with quantum speedup
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• Novel constructions for the fault-tolerant Toffoli gate
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Quantum computation of stopping power for inertial fusion target design
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
• Expressing and Analyzing Quantum Algorithms with Qualtran
• Efficient Implementation of Multi-Controlled Quantum Gates
• 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