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

arXiv:1904.01671

Decomposing Quantum Generalized Toffoli with an Arbitrary Number of Ancilla

Jonathan M. Baker, Casey Duckering, Hoover, Alexander, Frederic T. Chong

Published Apr 2, 2019• 9 citations
arXivHTMLPDF

Abstract

We present a general decomposition of the Generalized Toffoli, and for completeness, the multi-target gate using an arbitrary number of clean or dirty ancilla. While prior work has shown how to decompose the Generalized Toffoli using 0, 1, or $O(n)$ many clean ancilla and 0, 1, and $n-2$ dirty ancilla, we provide a generalized algorithm to bridge the gap, i.e. this work gives an algorithm to generate a decomposition for any number of clean or dirty ancilla. While it is hard to guarantee optimality, our decompositions guarantee a decrease in circuit depth as the number of ancilla increases.

DOI
10.48550/arxiv.1904.01671

Related papers

Decomposing (n+1)$(n+1)$‐Qubit Toffoli Gate with Shallow Circuit Depth and No Ancilla

Jian Leng, Fan Yang, Xiang‐Bin Wang

Abstract Circuit depth optimization is crucial for implementing quantum algorithms in practical systems. The decomposition of ‐qubit Toffoli gate is continually optimized since this gate is a fundamental component for many quantum algorithms. Without any ancilla, ‐qubit Toffoli gate can be decomposed by standard gates with circuit depth . Here, the decomposition is further optimized and its circuit depth is reduced to . The decomposition is equivalent to ‐qubit Toffoli gate up to an overall phase and also does not need any ancilla.

Advanced Quantum Technologies•Dec 20, 2023•2 citations

Optimal Multi-Bit Toffoli Gate Synthesis

Young-Min Jun, In-Chan Choi

Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.

IEEE Access•Jan 1, 2023•3 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

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

Exact space-depth trade-offs in multicontrolled Toffoli decomposition

Suman Dutta, Siyi Wang, Anubhab Baksi +2 more

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.

Physical Review A•May 14, 2025•6 citations

A Decomposition Method of MCT Gates for Reducing Overall Circuit T-depth

Zanhe Qi, Koki Hirono, David Clarino +1 more

It is considered to be very important to reduce so-called the T-depth of a target quantum circuit for realizing future fault-tolerant quantum computation. Thus, there have been many researches to consider how to decompose Multiple Controlled Toffoli (MCT) gates with few T-depth; these existing methods do not consider the T-depth of each qubit when they decompose one MCT gate. In contrast to existing methods, this paper proposes to consider the T-depth of each qubit when we decompose an MCT gate; we show that we can decrease the T-depth by considering the T-depth of each qubit and appropriately selecting ancilla qubits and decomposition methods. In addition, to consider the impact of the decomposition of one MCT gate on the decomposition of subsequent gates, our method utilizes beam search to select a possibly best decomposition for each MCT gate. We confirmed that the proposed method can reduce the T-depth by an average of 17.1% compared to existing methods.

IPSJ Transactions on System and LSI Design Methodology•Jan 1, 2026•0 citations
We present a general decomposition of the Generalized Toffoli, and for completeness, the multi-target gate using an arbitrary number of clean or dirty ancilla. While prior work has shown how to decompose the Generalized Toffoli using 0, 1, or O(n)O(n)O(n) many clean ancilla and 0, 1, and n−2n-2n−2 dirty ancilla, we provide a generalized algorithm to bridge the gap, i.e. this work gives an algorithm to generate a decomposition for any number of clean or dirty ancilla. While it is hard to guarantee optimality, our decompositions guarantee a decrease in circuit depth as the number of ancilla increases.
Decomposing (n+1)(n+1)(n+1)(n+1)‐Qubit Toffoli Gate with Shallow Circuit Depth and No Ancilla
Abstract Circuit depth optimization is crucial for implementing quantum algorithms in practical systems. The decomposition of ‐qubit Toffoli gate is continually optimized since this gate is a fundamental component for many quantum algorithms. Without any ancilla, ‐qubit Toffoli gate can be decomposed by standard gates with circuit depth . Here, the decomposition is further optimized and its circuit depth is reduced to . The decomposition is equivalent to ‐qubit Toffoli gate up to an overall phase and also does not need any ancilla.
Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.
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.
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 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{\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 TTT depth in the Clifford+T\text{Clifford}+TClifford+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\text{Clifford}+TClifford+T gate set, various methodologies are also explored in this regard for trade-off-related implications.
It is considered to be very important to reduce so-called the T-depth of a target quantum circuit for realizing future fault-tolerant quantum computation. Thus, there have been many researches to consider how to decompose Multiple Controlled Toffoli (MCT) gates with few T-depth; these existing methods do not consider the T-depth of each qubit when they decompose one MCT gate. In contrast to existing methods, this paper proposes to consider the T-depth of each qubit when we decompose an MCT gate; we show that we can decrease the T-depth by considering the T-depth of each qubit and appropriately selecting ancilla qubits and decomposition methods. In addition, to consider the impact of the decomposition of one MCT gate on the decomposition of subsequent gates, our method utilizes beam search to select a possibly best decomposition for each MCT gate. We confirmed that the proposed method can reduce the T-depth by an average of 17.1% compared to existing methods.