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

IPSJ Transactions on System and LSI Design Methodology

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

Zanhe Qi, Koki Hirono, David Clarino, Shigeru Yamashita

Published Jan 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.2197/ipsjtsldm.19.12

Related papers

A Decomposition Method for MCT Gates Considering T-depth of Each Qubit

Zhijun Qi, Kouki Hirono, David Clarino +1 more

For realizing future fault-tolerant quantum computation, it is very important to reduce so-called the T-depth of a target quantum circuit. Thus, there have been many researches to consider how to decompose Multiple Controlled Toffoli (MCT) gates with few T-depth; these existing methods does 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 Tdepth of each bit 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.

IEEE Computer Society Annual Symposium on VLSI•Jul 6, 2025•1 citation

Reducing T-depth in Quantum Oracles via Simultaneous Decomposition of MCT Gates

Zanhe Qi, David Clarino, Shigeru Yamashita +1 more

This paper presents a heuristic for reducing T-depth in quantum circuits by jointly decomposing multiple multi-controlled Toffoli (MCT) gates with careful selection of control and ancilla qubits. Our experimental results show that our method achieves an average 58.06% reduction in overall T-depth in designed quantum oracles compared with existing decompositions. We further estimate the actual runtime of solving a 45-variable SAT problem on a future fault-tolerant quantum computer and show that our method reduces the execution time to 48.5% of that of a conventionally generated circuit; our result gives a concrete example of a search problem where a fault-tolerant quantum computer would outperform a classical one with a brute-force method.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 19, 2026•0 citations

Minimum Toffoli depth for the multi-controlled Toffoli gate via teleportation

Spyros Tserkis, Muhammad Umer, Eleftherios Mastorakis +1 more

The decomposition of complex quantum operations into experimentally feasible gate sets has been a central challenge since the early development of quantum computing. The multi-controlled Toffoli (MCT) gate is a key example, with applications across a wide range of quantum algorithms, whose decomposition into smaller gates, however, typically leads to deep circuits. In this work, we introduce a teleportation-based decomposition that implements an MCT gate. This decomposition has unit Toffoli depth, independent of the number of controls, while achieving the lowest Toffoli count among existing approaches for more than five controls at the cost of a linear overhead in ancilla qubits. We also investigate the parameter regimes in which the teleportation-based decomposition is preferable by analyzing the relative quality of distributed entanglement and Toffoli gates. We further demonstrate the advantages of this implementation in circuits that rely on MCT gates, such as the adder operator, quantum read-only memory, quantum neurons, and quantum decision trees.

quant-pharXiv:2604.25861•Apr 29, 2026•0 citations

Device-Aware Decomposition and Mapping of Multiple-Control Toffoli Circuits in Quantum Computing Systems

Yibo Jiang, Xueyun Cheng, Pengcheng Zhu +2 more

Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.

•Sep 13, 2024•0 citations

Reducing T-count When Decomposing Many MPMCT Gates Simultaneously

Soma Esaki, Shigeru Yamashita

To realize fault-tolerant quantum circuits, one of the important task is to reduce the number of T gates (T-count) when we decompose MPMCT (Mixed Polarity Multiple-Control Toffoli) gates into elementary gates. When we have enough auxiliary qubits, we have an efficient decomposition of a single MPMCT gate. However, it has not been studied intensively how to decompose many MPMCT gates efficiently at the same time. Thus, this paper studies what is an efficient decomposition method when we have many MPMCT gates. We consider two situations to reduce T-count when we need to decompose many MPMCT gates. Then, we propose a heuristic method to reorder MPMCT gates if possible so that we can find the two situations as much as possible. Our preliminary experiments show that our heuristic can reduce T-count drastically.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Nov 1, 2020•3 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
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.
For realizing future fault-tolerant quantum computation, it is very important to reduce so-called the T-depth of a target quantum circuit. Thus, there have been many researches to consider how to decompose Multiple Controlled Toffoli (MCT) gates with few T-depth; these existing methods does 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 Tdepth of each bit 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.
This paper presents a heuristic for reducing T-depth in quantum circuits by jointly decomposing multiple multi-controlled Toffoli (MCT) gates with careful selection of control and ancilla qubits. Our experimental results show that our method achieves an average 58.06% reduction in overall T-depth in designed quantum oracles compared with existing decompositions. We further estimate the actual runtime of solving a 45-variable SAT problem on a future fault-tolerant quantum computer and show that our method reduces the execution time to 48.5% of that of a conventionally generated circuit; our result gives a concrete example of a search problem where a fault-tolerant quantum computer would outperform a classical one with a brute-force method.
The decomposition of complex quantum operations into experimentally feasible gate sets has been a central challenge since the early development of quantum computing. The multi-controlled Toffoli (MCT) gate is a key example, with applications across a wide range of quantum algorithms, whose decomposition into smaller gates, however, typically leads to deep circuits. In this work, we introduce a teleportation-based decomposition that implements an MCT gate. This decomposition has unit Toffoli depth, independent of the number of controls, while achieving the lowest Toffoli count among existing approaches for more than five controls at the cost of a linear overhead in ancilla qubits. We also investigate the parameter regimes in which the teleportation-based decomposition is preferable by analyzing the relative quality of distributed entanglement and Toffoli gates. We further demonstrate the advantages of this implementation in circuits that rely on MCT gates, such as the adder operator, quantum read-only memory, quantum neurons, and quantum decision trees.
Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.
To realize fault-tolerant quantum circuits, one of the important task is to reduce the number of T gates (T-count) when we decompose MPMCT (Mixed Polarity Multiple-Control Toffoli) gates into elementary gates. When we have enough auxiliary qubits, we have an efficient decomposition of a single MPMCT gate. However, it has not been studied intensively how to decompose many MPMCT gates efficiently at the same time. Thus, this paper studies what is an efficient decomposition method when we have many MPMCT gates. We consider two situations to reduce T-count when we need to decompose many MPMCT gates. Then, we propose a heuristic method to reorder MPMCT gates if possible so that we can find the two situations as much as possible. Our preliminary experiments show that our heuristic can reduce T-count drastically.
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.