Abstract

Since an n-qubit circuit consisting of CNOT gates can have up to \Omega(n^2/\log{n}) CNOT gates, it is natural to expect that \Omega(n^2/\log{n}) Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision \epsilon in T-depth exactly 1 using a universal \lceil\log_2(8/\epsilon)\rceil-qubit catalyst state.

Personal information

Tuomas Laakkonen is a PhD student at MIT, with research interests including fault-tolerant quantum circuit optimization and quantum algorithms for differential equations. Previously, Tuomas was a research scientist at Quantinuum, working on quantum algorithms for approximating topological invariants, and did a master's degree at the University of Oxford, studying the connection between tensor network methods and complexity theory.

Reference

https://arxiv.org/abs/2512.24982