We give a $\text{Clifford}+T$ representation of the Toffoli gate of $T$-depth one, using four ancillas. More generally, we describe a class of circuits whose $T$-depth can be reduced to one by using sufficiently many ancillas. We show that the cost of adding an additional control to any controlled gate is at most eight additional $T$ gates and $T$-depth two. We also show that the circuit $THT$ does not possess a $T$-depth one representation with an arbitrary number of ancillas initialized to $|0\ensuremath{\rangle}$.
We give a Clifford+T representation of the Toffoli gate of T-depth one, using four ancillas. More generally, we describe a class of circuits whose T-depth can be reduced to one by using sufficiently many ancillas. We show that the cost of adding an additional control to any controlled gate is at most eight additional T gates and T-depth two. We also show that the circuit THT does not possess a T-depth one representation with an arbitrary number of ancillas initialized to ∣0\ensuremath⟩.
Since an n-qubit circuit consisting of CNOT gates can have up to Ω(n2/logn) CNOT gates, it is natural to expect that Ω(n2/logn) 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 ε in T-depth exactly 1 using a universal ⌈log2(8/ε)⌉-qubit catalyst state.
We present two constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four $T=\mathrm{exp}(i\ensuremath{\pi}{\ensuremath{\sigma}}^{z}/8)$ gates, whereas conventional circuits require seven T gates. An extension of this result is that adding n control inputs to a controlled gate requires 4nT gates, whereas the best prior result was 8n. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\ensuremath{\sigma}}^{z}$ error occurring with probability p in any one of eight T gates required to produce the Toffoli gate. By postselecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from 4p (or 7p, without the first contribution) to 28p2 for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.
In this paper we consider the optimized implementation of multicontrolled Toffoli decomposition using the Clifford+T gate set. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulas) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli gate) of the n-controlled Toffoli decomposition and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli (consequently T) depth, which is an extension of the technique introduced by Khattar and Gidney [T. Khattar and C. Gidney, arXiv:2407.17966]. In terms of a negative result, we first show that by using such conditionally clean ancilla techniques, the Toffoli depth can never achieve exactly $\ensuremath{\lceil}{log}_{2}n\ensuremath{\rceil}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancillas [J. Nie et al., arXiv:2402.05053; T. Khattar and C. Gidney, arXiv:2407.17966]. Then we prove that, in a more general setup, the T depth in the Clifford+T decomposition, via Toffoli gates, is lower bounded by $\ensuremath{\lceil}{log}_{2}n\ensuremath{\rceil}$, and this bound is achieved following the complete binary tree structure. Since the (2-controlled) Toffoli gate can further be decomposed using Clifford+T gate set, various methodologies are also explored in this regard for trade-off-related implications.
Multiqubit quantum gates are natural quantum operations derived from various decompositions of quantum evolutions. Recently, linear-depth quantum circuits were proposed for an arbitrary n-qubit Toffoli gate with ancillary qubits [M. Saeedi and M. Pedram, Phys. Rev. A 87, 062318 (2013)]. Their circuits are based on an equivalent representation of the not gate regardless of the global phase. However, we find that this equivalence cannot be extended to the controlled-not gate or the n-qubit Toffoli gate. By reevaluating their circuits, we argue that their linear-depth quantum circuits could realize the joint operations of an n-qubit Toffoli gate and an n-qubit phase-flip gate.
In this paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford + T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the n-controlled Toffoli (hereform we will tell n-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the (2-controlled) Toffoli gate can further be decomposed using Clifford + T, various methodologies are explored too in this regard for trade-off related implications.
Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford+P9 Gates
Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths n=2h−1, the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires 6n+3 logical P9 injections and 4n−3 clean ancillary qutrits. It matches the direct P9 count of a recursively extended Clifford+P9 baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the 6n+3P9 count but has depth O(logm+n−m) for a balanced core m=2h−1≤n, which is linear in the worst case over n. By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.