Quantum circuits of T-depth one

Understand

We give a Clifford+T representation of the Toffoli gate of T-depth 1, using four ancillas.

• More generally, we describe a class of circuits whose T-depth can be reduced to 1 by using sufficiently many ancillas.
• We show that the cost of adding an additional control to any controlled gate is at most 8 additional T-gates, and T-depth 2.
• We also show that the circuit THT does not possess a T-depth 1 representation with an arbitrary number of ancillas initialized to 0.