Publication
Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla
Abhoy Kole; Majd Assaad; Till Schnittka; Rolf Drechsler
In: IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE Computer Society Annual Symposium on VLSI (ISVLSI-2026), July 7-10, Kolkata, India, 2026.
Abstract
Multi-controlled Toffoli gates are fundamental
building blocks in quantum computation, with applications in
quantum arithmetic, simulation, and search algorithms. In faulttolerant 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