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:1210.0974 · Physical Review A

Quantum circuits of T -depth one

Peter Selinger

Published Apr 1, 2013• 254 citations
arXivHTMLPDF

Abstract

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}$.

DOI
10.1103/physreva.87.042302

Related papers

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•6 citations

Low-overhead constructions for the fault-tolerant Toffoli gate

Cody Jones

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 $4n$ $T$ 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 $28{p}^{2}$ 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.

arXiv:1212.5069•Physical Review A•Feb 20, 2013•244 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.

arXiv:2502.01433•Physical Review A•May 14, 2025•11 citations

Comment on “Linear-depth quantum circuits for n -qubit Toffoli gates with no ancilla”

Ming-Xing Luo, Hui-Ran Li

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.

Physical Review A•Aug 18, 2016•4 citations

Primitive quantum gate realizations of multiple-controlled Toffoli gates

Mozammel H. A. Khan

Multiple-controlled Toffoli gates are extensively used in quantum and reversible circuits. However, very limited attempt has been made for primitive quantum gate realizations of these gates. In this paper, we present realization of three-qubit Toffoli gate requiring five primitive quantum gates. We then propose realization of four-qubit Toffoli gate requiring 13 primitive quantum gates and one ancilla input. Finally, we propose realizations of (n + 1)-qubit (n > 3 control lines) Toffoli gates using (⌈n/2⌉ + 1)-qubit and (⌊n/2⌋ + 1)-qubit Toffoli gates and ancilla inputs, which make a trade off between quantum cost and number of ancilla inputs. Our proposed method outperforms the best result so far presented in the literature in terms of quantum cost and number of ancilla inputs.

International Conference on Computer and Information Technology (ICCIT)•Mar 1, 2014•1 citation

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•1 citation
We give a Clifford+T\text{Clifford}+TClifford+T representation of the Toffoli gate of TTT-depth one, using four ancillas. More generally, we describe a class of circuits whose TTT-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 TTT gates and TTT-depth two. We also show that the circuit THTTHTTHT does not possess a TTT-depth one representation with an arbitrary number of ancillas initialized to ∣0\ensuremath⟩|0\ensuremath{\rangle}∣0\ensuremath⟩.
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.
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 TTT gates. An extension of this result is that adding nnn control inputs to a controlled gate requires 4n4n4n TTT gates, whereas the best prior result was 8n8n8n. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\ensuremath{\sigma}}^{z}$ error occurring with probability ppp in any one of eight TTT 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 4p4p4p (or 7p7p7p, without the first contribution) to 28p228{p}^{2}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\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.
Multiqubit quantum gates are natural quantum operations derived from various decompositions of quantum evolutions. Recently, linear-depth quantum circuits were proposed for an arbitrary nnn-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 nnn-qubit Toffoli gate. By reevaluating their circuits, we argue that their linear-depth quantum circuits could realize the joint operations of an nnn-qubit Toffoli gate and an nnn-qubit phase-flip gate.
Multiple-controlled Toffoli gates are extensively used in quantum and reversible circuits. However, very limited attempt has been made for primitive quantum gate realizations of these gates. In this paper, we present realization of three-qubit Toffoli gate requiring five primitive quantum gates. We then propose realization of four-qubit Toffoli gate requiring 13 primitive quantum gates and one ancilla input. Finally, we propose realizations of (n + 1)-qubit (n > 3 control lines) Toffoli gates using (⌈n/2⌉ + 1)-qubit and (⌊n/2⌋ + 1)-qubit Toffoli gates and ancilla inputs, which make a trade off between quantum cost and number of ancilla inputs. Our proposed method outperforms the best result so far presented in the literature in terms of quantum cost and number of ancilla inputs.
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.