Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Exact space-depth trade-offs in multicontrolled Toffoli decomposition

Suman Dutta, Siyi Wang, Anubhab Baksi, Anupam Chattopadhyay, Subhamoy Maitra

Published May 14, 2025• 6 citations
Publisher

Abstract

In this paper we consider the optimized implementation of multicontrolled Toffoli decomposition using the $\text{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 $\text{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 $\text{Clifford}+T$ gate set, various methodologies are also explored in this regard for trade-off-related implications.

DOI
10.1103/physreva.111.052611

Related papers

Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla

Abhoy Kole, Majd Assaad, Till Schnittka +1 more

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.

quant-pharXiv:2605.18169•May 19, 2026•0 citations

On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition

Dutta, Suman, Siyi Wang, Anubhab Baksi +2 more

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.

arXiv:2502.01433•Feb 3, 2025•0 citations

Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

Amit Saha, Francesco Arzani

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=2^h-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 $P_9$ injections and $\frac{n-3}{4}$ clean ancillary qutrits. It matches the direct $P_9$ count of a recursively extended Clifford+$P_9$ 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+3$ $P_9$ count but has depth $O(\log m+n-m)$ for a balanced core $m=2^h-1\leq 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.

quant-pharXiv:2609.29884•Sep 25, 2026•0 citations

Any Clifford+T circuit can be controlled with constant T-depth overhead

Isaac H. Kim, Tuomas Laakkonen

Since an n-qubit circuit consisting of CNOT gates can have up to $Ω(n^2/\log{n})$ CNOT gates, it is natural to expect that $Ω(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 $ε$ in T-depth exactly 1 using a universal $\lceil\log_2(8/ε)\rceil$-qubit catalyst state.

quant-pharXiv:2512.24982•Jan 1, 2026•0 citations

Logarithmic-depth MCT gate implementation method on a given arbitrary number of clean ancillae

Jongheon Lee, Yousung Kang

Abstract One of the key operations in various quantum algorithms, including Grover’s algorithm, is the multi-controlled Toffoli (MCT) gate. This work proposes optimal design techniques for the MCT gate using the conditionally clean ancillae strategy, assuming that an arbitrary number of clean ancillae are available. We consider two primary cases: first, when only a single clean ancilla is available; and second, when the number of clean ancillae is $$\mathcal {O}(n)$$ O ( n ) , where n is the number of controls in the MCT gate. For the case of a single clean ancilla, we propose a novel design method that achieves better efficiency compared to a previous approach. While prior work yields a Toffoli-depth of $$\mathcal {O}(n)$$ O ( n ) , our proposed method reduces the Toffoli-depth to $$\mathcal {O}(\sqrt{n})$$ O ( n ) . Moreover, by employing this new technique as a subroutine within previously proposed methods for the cases of two or three clean ancillae, we demonstrate both logically and empirically an improvement in time complexity. Additionally, prior work addressed optimal designs only when the number of clean ancillae was up to approximately $$\log n$$ log n , without providing efficient strategies beyond this regime. In this study, we also present efficient MCT gate constructions when a sufficiently large number of clean ancillae are available. We confirm, both theoretically and empirically, that the Toffoli-depth decreases as the number of clean ancillae increases. In conclusion, this work highlights that the optimal MCT design strategy depends on the availability of clean ancillae. It also indirectly suggests a threshold point at which the optimal design strategy transitions, depending on the number of ancillae provided.

Quantum Information Processing•Jan 20, 2026•0 citations

Optimal T-depth Quantum Circuits for Implementing Arbitrary Boolean Functions

Suman Dutta, Anik Bhaumik, Anupam Chattopadhyay +1 more

Abstract In this paper, we present a generic construction for synthesizing an optimal T-depth quantum circuit for any arbitrary n -input, m -output Boolean function f : {0, 1 } n → {0, 1} m with algebraic degree k ≤ n , achieving an exact Toffoli (consequently T) depth of ⌈log 2 k ⌉. This broadly generalizes the recent result establishing the optimal Toffoli (and T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). The optimality of T-depth in this initiative is considered in the context of implementing an n -MCT, assuming the decomposition via Clifford plus Toffoli gates. The key technique involves inspecting the Algebraic Normal Form (ANF) of the Boolean function. Obtaining a benchmark for the minimum T-depth of such circuits is crucial for the efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The broader implications of our results include a provable lower bounds on T-depth for S-box and block cipher implementations, such as AES. Finally, we also explain the impact of our result in identifying the T-depth for the generic cryptanalysis of block ciphers using Grover’s algorithm.

Quantum Information and Computation•Dec 1, 2025•2 citations
In this paper we consider the optimized implementation of multicontrolled Toffoli decomposition using the Clifford+T\text{Clifford}+TClifford+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 nnn-controlled Toffoli decomposition and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli (consequently TTT) 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⌈log2n\ensuremath⌉\ensuremath{\lceil}{log}_{2}n\ensuremath{\rceil}\ensuremath⌈log2​n\ensuremath⌉, 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 TTT depth in the Clifford+T\text{Clifford}+TClifford+T decomposition, via Toffoli gates, is lower bounded by \ensuremath⌈log2n\ensuremath⌉\ensuremath{\lceil}{log}_{2}n\ensuremath{\rceil}\ensuremath⌈log2​n\ensuremath⌉, and this bound is achieved following the complete binary tree structure. Since the (2-controlled) Toffoli gate can further be decomposed using Clifford+T\text{Clifford}+TClifford+T gate set, various methodologies are also explored in this regard for trade-off-related implications.
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.
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 nnn-controlled Toffoli (hereform we will tell nnn-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 (222-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+P_9+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−1n=2^h-1n=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+36n+36n+3 logical P9P_9P9​ injections and n−34\frac{n-3}{4}4n−3​ clean ancillary qutrits. It matches the direct P9P_9P9​ count of a recursively extended Clifford+P9P_9P9​ 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+36n+36n+3 P9P_9P9​ count but has depth O(log⁡m+n−m)O(\log m+n-m)O(logm+n−m) for a balanced core m=2h−1≤nm=2^h-1\leq nm=2h−1≤n, which is linear in the worst case over nnn. 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/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) CNOT gates, it is natural to expect that Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(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 ⌈log⁡2(8/ε)⌉\lceil\log_2(8/ε)\rceil⌈log2​(8/ε)⌉-qubit catalyst state.
Abstract One of the key operations in various quantum algorithms, including Grover’s algorithm, is the multi-controlled Toffoli (MCT) gate. This work proposes optimal design techniques for the MCT gate using the conditionally clean ancillae strategy, assuming that an arbitrary number of clean ancillae are available. We consider two primary cases: first, when only a single clean ancilla is available; and second, when the number of clean ancillae is O(n)\mathcal {O}(n)O(n) O ( n ) , where n is the number of controls in the MCT gate. For the case of a single clean ancilla, we propose a novel design method that achieves better efficiency compared to a previous approach. While prior work yields a Toffoli-depth of O(n)\mathcal {O}(n)O(n) O ( n ) , our proposed method reduces the Toffoli-depth to O(n)\mathcal {O}(\sqrt{n})O(n​) O ( n ) . Moreover, by employing this new technique as a subroutine within previously proposed methods for the cases of two or three clean ancillae, we demonstrate both logically and empirically an improvement in time complexity. Additionally, prior work addressed optimal designs only when the number of clean ancillae was up to approximately log⁡n\log nlogn log n , without providing efficient strategies beyond this regime. In this study, we also present efficient MCT gate constructions when a sufficiently large number of clean ancillae are available. We confirm, both theoretically and empirically, that the Toffoli-depth decreases as the number of clean ancillae increases. In conclusion, this work highlights that the optimal MCT design strategy depends on the availability of clean ancillae. It also indirectly suggests a threshold point at which the optimal design strategy transitions, depending on the number of ancillae provided.
Abstract In this paper, we present a generic construction for synthesizing an optimal T-depth quantum circuit for any arbitrary n -input, m -output Boolean function f : {0, 1 } n → {0, 1} m with algebraic degree k ≤ n , achieving an exact Toffoli (consequently T) depth of ⌈log 2 k ⌉. This broadly generalizes the recent result establishing the optimal Toffoli (and T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). The optimality of T-depth in this initiative is considered in the context of implementing an n -MCT, assuming the decomposition via Clifford plus Toffoli gates. The key technique involves inspecting the Algebraic Normal Form (ANF) of the Boolean function. Obtaining a benchmark for the minimum T-depth of such circuits is crucial for the efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The broader implications of our results include a provable lower bounds on T-depth for S-box and block cipher implementations, such as AES. Finally, we also explain the impact of our result in identifying the T-depth for the generic cryptanalysis of block ciphers using Grover’s algorithm.