Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant 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.
Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant 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.
The Toffoli gate is a fundamental building block for quantum arithmetic and reversible logic, yet its efficient realization remains a major challenge in both near-term and fault-tolerant quantum architectures. Recent advances in dynamic quantum circuit capabilities, including mid-circuit measurement and classical feedforward, provide new opportunities for reducing the resource overhead of non-Clifford operations.
In this work, we propose a set of dynamic decomposition strategies for multi-controlled Toffoli gates that exploit adaptive circuit execution and ancilla-assisted constructions. Our methods systematically reduce entangling-gate count, T-count, and T-depth compared with conventional static decompositions, while preserving fault-tolerance guarantees. Through analytical cost models and experimental evaluation, we demonstrate that relative-phase primitives and measurement-conditioned corrections enable scalable implementations with improved depth and resource efficiency.
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.
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.
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.
In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.
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.