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 Computer Society Annual Symposium on VLSI

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

Zhijun Qi, Kouki Hirono, David Clarino, Shigeru Yamashita

Published Jul 6, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1109/isvlsi65124.2025.11130329

Related papers

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

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

Optimal Toffoli-Depth Multi-Controlled Toffoli Decomposition in 2D Qubit Layout

Anik Basu Bhaumik, Suman Dutta, Anupam Chattopadhyay

The multi-controlled Toffoli (MCT) gate is a key primitive in quantum arithmetic, oracle construction, and quantum cryptanalysis. Although recent work has established optimal Toffoli-depth MCT decompositions under all-to-all qubit connectivity, their realization on near-term quantum hardware with restricted qubit connectivity remains largely unexplored. While general-purpose quantum mappers can route arbitrary circuits, they do not explicitly exploit the repeated interaction patterns inherent in MCT decompositions. In our present paper, we study architecture-aware mappings of optimal Toffoli-depth MCT decompositions onto restricted two-dimensional qubit layouts. We begin with a structured geometric placements that preserve the parallelism of state-of-the-art Toffoli and MCT decompositions with no additional depth overhead. We further introduce a motif-based packing framework in which decomposition layers are represented by interaction motifs derived from basic Toffoli gates. By embedding these motifs vertex-disjointly into hardware graphs, we characterize the minimum-size topologies supporting the required qubit resources and derive explicit bounds on the resulting depth overhead under tight qubit budgets. Finally, we compare these bounds with routing-aware placement heuristics and empirically evaluate the effectiveness of embedding different motifs across a range of hardware topologies.

quant-pharXiv:2606.15113•Jun 16, 2026•0 citations
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.
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.
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.
The multi-controlled Toffoli (MCT) gate is a key primitive in quantum arithmetic, oracle construction, and quantum cryptanalysis. Although recent work has established optimal Toffoli-depth MCT decompositions under all-to-all qubit connectivity, their realization on near-term quantum hardware with restricted qubit connectivity remains largely unexplored. While general-purpose quantum mappers can route arbitrary circuits, they do not explicitly exploit the repeated interaction patterns inherent in MCT decompositions. In our present paper, we study architecture-aware mappings of optimal Toffoli-depth MCT decompositions onto restricted two-dimensional qubit layouts. We begin with a structured geometric placements that preserve the parallelism of state-of-the-art Toffoli and MCT decompositions with no additional depth overhead. We further introduce a motif-based packing framework in which decomposition layers are represented by interaction motifs derived from basic Toffoli gates. By embedding these motifs vertex-disjointly into hardware graphs, we characterize the minimum-size topologies supporting the required qubit resources and derive explicit bounds on the resulting depth overhead under tight qubit budgets. Finally, we compare these bounds with routing-aware placement heuristics and empirically evaluate the effectiveness of embedding different motifs across a range of hardware topologies.