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

IEEE International Symposium on Multiple-Valued Logic (ISMVL)

T-depth Optimization for Fault-Tolerant Quantum Circuits

Philipp Niemann, Anshu Gupta, Rolf Drechsler

Published May 1, 2019• 22 citations
Publisher

Abstract

The Clifford+T gate library consisting of Hadamard, T, and CNOT gates has attracted much interest in quantum circuit synthesis, particularly due to its applicability to fault tolerant realizations. Since fault tolerant implementations of the T gate have very high latency, recent work in this area is aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to exploit additional ancilla qubits in the mapping of reversible circuits consistina of multiple controlled Toffoli gates (MCT gates) into califford+T quantum circuits, with the primary optimization objective to minimize the T-depth. Our proposed approach takes advantage of and generalizes earlier work on corresponding mapping algorithms. An experimental evaluation shows that our approach leads to a significant T-depth reduction compared to earlier approaches.

DOI
10.1109/ismvl.2019.00027

Related papers

Technology Mapping of Reversible Circuits to Clifford+T Quantum Circuits

Nabila Abdessaied, Matthew Amy, Mathias Soeken +1 more

The Clifford+T quantum gate library has attracted much interest in the design of quantum circuits, particularly since the contained operations can be implemented in a fault-tolerant manner. Since fault tolerant implementations of the T gate have very high latency, synthesis and optimization are aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to map mixed polarity multiple controlled Toffoli gates into Clifford+T quantum circuits. Our approach is based on the multiple control Toffoli mapping algorithms proposed by Barenco et al., which are given T-depth optimized Clifford+T translations. Experiments show that our approach leads to a significant T-depth reduction of 54% on average.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2016•48 citations

The Optimization and Application of 3-Bit Hermitian Gates and Multiple Control Toffoli Gates

Hai-Sheng Li

The well-known 3-bit Hermitian gate (a Toffoli gate) has been implemented using Clifford + T circuits. Compared with the Peres gate, its implementation circuit requires more controlled-NOT (CNOT) gates. However, the Peres gate is not Hermitian. This paper reports four 3-bit Hermitian gates named LI gates. Whose realized circuits have the same T-count, T-depth, and CNOT-count as the Peres gate. Furthermore, two decomposition methods of a multiple control Toffoli (MCT) gate are proposed for different primary optimization goals. Then, we design the equality, less-than, and full comparators with the minimum circuit width using proposed Hermitian gates and optimized MCT gates. A fault-tolerant circuit is required for robust quantum computing. Clifford+T circuits are accepted solutions for fault-tolerant implementation. Considering T-count, T-depth, CNOT-count, and circuit width as the primary optimization goals, we design the optimized Clifford + T circuits of three comparators using LI gates and optimized MCT gates. Comparison and analysis show that the proposed comparators have better overall performances for T-count, T-depth, CNOT-count, and circuit width than the best-known comparators without quantum measurements.

IEEE Transactions on Quantum Engineering•Jan 1, 2022•6 citations

Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning

Matthew Amy, Dmitri A Maslov, Michele Mosca

Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to resynthesize circuits with ancillae at effectively no additional cost, allowing space-time trade-offs to be easily explored. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.

arXiv:1303.2042•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Sep 16, 2014•277 citations

Techniques for fault-tolerant decomposition of a multicontrolled Toffoli gate

Laxmidhar Biswal, Debjyoti Bhattacharjee, Anupam Chattopadhyay +1 more

Physical implementation of scalable quantum architectures faces an immense challenge in the form of fragile quantum states. To overcome it, quantum architectures with fault tolerance are desirable. These are achieved currently by using a surface code along with a transversal gate set. This indicates the need for decomposition of universal $n$-qubit multicontrolled Toffoli ($n$-MCT) gates using a transversal gate set. Additionally, the transversal non-Clifford phase gate incurs high latency, which makes it an important factor to consider during decomposition. Additionally, the decomposition of a large MCT gate without ancillas presents an additional hurdle. In this paper, we address both of these issues by introducing the $\mathrm{Clifford}+{Z}_{N}$ gate library. We present an ancilla-free decomposition of MCT gates with linear phase depth and quadratic phase count. Furthermore, we provide a technique for decomposition of MCT gates in unit phase depth using the $\mathrm{Clifford}+{Z}_{N}$ library, albeit at the cost of ancillary lines and exponential phase count.

arXiv:1904.06920•Physical Review A•Dec 19, 2019•27 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

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
The Clifford+T gate library consisting of Hadamard, T, and CNOT gates has attracted much interest in quantum circuit synthesis, particularly due to its applicability to fault tolerant realizations. Since fault tolerant implementations of the T gate have very high latency, recent work in this area is aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to exploit additional ancilla qubits in the mapping of reversible circuits consistina of multiple controlled Toffoli gates (MCT gates) into califford+T quantum circuits, with the primary optimization objective to minimize the T-depth. Our proposed approach takes advantage of and generalizes earlier work on corresponding mapping algorithms. An experimental evaluation shows that our approach leads to a significant T-depth reduction compared to earlier approaches.
The Clifford+T quantum gate library has attracted much interest in the design of quantum circuits, particularly since the contained operations can be implemented in a fault-tolerant manner. Since fault tolerant implementations of the T gate have very high latency, synthesis and optimization are aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to map mixed polarity multiple controlled Toffoli gates into Clifford+T quantum circuits. Our approach is based on the multiple control Toffoli mapping algorithms proposed by Barenco et al., which are given T-depth optimized Clifford+T translations. Experiments show that our approach leads to a significant T-depth reduction of 54% on average.
The well-known 3-bit Hermitian gate (a Toffoli gate) has been implemented using Clifford + T circuits. Compared with the Peres gate, its implementation circuit requires more controlled-NOT (CNOT) gates. However, the Peres gate is not Hermitian. This paper reports four 3-bit Hermitian gates named LI gates. Whose realized circuits have the same T-count, T-depth, and CNOT-count as the Peres gate. Furthermore, two decomposition methods of a multiple control Toffoli (MCT) gate are proposed for different primary optimization goals. Then, we design the equality, less-than, and full comparators with the minimum circuit width using proposed Hermitian gates and optimized MCT gates. A fault-tolerant circuit is required for robust quantum computing. Clifford+T circuits are accepted solutions for fault-tolerant implementation. Considering T-count, T-depth, CNOT-count, and circuit width as the primary optimization goals, we design the optimized Clifford + T circuits of three comparators using LI gates and optimized MCT gates. Comparison and analysis show that the proposed comparators have better overall performances for T-count, T-depth, CNOT-count, and circuit width than the best-known comparators without quantum measurements.
Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to resynthesize circuits with ancillae at effectively no additional cost, allowing space-time trade-offs to be easily explored. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.
Physical implementation of scalable quantum architectures faces an immense challenge in the form of fragile quantum states. To overcome it, quantum architectures with fault tolerance are desirable. These are achieved currently by using a surface code along with a transversal gate set. This indicates the need for decomposition of universal nnn-qubit multicontrolled Toffoli (nnn-MCT) gates using a transversal gate set. Additionally, the transversal non-Clifford phase gate incurs high latency, which makes it an important factor to consider during decomposition. Additionally, the decomposition of a large MCT gate without ancillas presents an additional hurdle. In this paper, we address both of these issues by introducing the Clifford+ZN\mathrm{Clifford}+{Z}_{N}Clifford+ZN​ gate library. We present an ancilla-free decomposition of MCT gates with linear phase depth and quadratic phase count. Furthermore, we provide a technique for decomposition of MCT gates in unit phase depth using the Clifford+ZN\mathrm{Clifford}+{Z}_{N}Clifford+ZN​ library, albeit at the cost of ancillary lines and exponential phase count.
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.
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.