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)

Reducing T-count When Decomposing Many MPMCT Gates Simultaneously

Soma Esaki, Shigeru Yamashita

Published Nov 1, 2020• 3 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl49045.2020.00-35

Related papers

An Efficient Method to Decompose and Map MPMCT Gates That Accounts for Qubit Placement

Atsushi Matsuo, Wakaki Hattori, Shigeru Yamashita

Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates are generally used to implement large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that invariably has a physical limitation, which means we need to (1) decompose the MPMCT gates into one- or two-qubit gates, and then (2) insert SWAP gates so that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have only been studied independently. In this work, we investigate that the total number of gates in a circuit can be decreased if the above two processes are considered simultaneously as a single step. We developed a method that inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Also, we consider the effect on the latter part of a circuit carefully by considering the qubit placement when decomposing an MPMCT gate. Experimental results demonstrate the effectiveness of our method.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Aug 9, 2022•3 citations

Dynamical Decomposition and Mapping of MPMCT Gates to Nearest Neighbor Architectures

Atsushi Matsuo, Wakaki Hattori, Shigeru Yamashita

We usually use Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates to realize large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that has some physical limitation; (1) we need to decompose MPMCT gates into one or two-qubit gates, and then (2) we need to insert SWAP gates such that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have been independently studied intensively. This paper points out that we can decrease the total number of the gates in a circuit if the above two processes are considered dynamically as a single step; we propose a method to inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Our additional idea is to consider the effect on the latter part of a circuit carefully by considering the qubit layout when composing an MPMCT gate. We show some experimental results to confirm the effectiveness of our method.

IEICE Technical Report; IEICE Tech. Rep.•Feb 24, 2021•0 citations

Dynamical Decomposition and Mapping of MPMCT Gates to Nearest Neighbor Architectures

Atsushi Matsuo, Wakaki Hattori, Shigeru Yamashita

We usually use Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates to realize large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that has some physical limitation; (1) we need to decompose MPMCT gates into one or two-qubit gates, and then (2) we need to insert SWAP gates such that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have been independently studied intensively. This paper points out that we can decrease the total number of the gates in a circuit if the above two processes are considered dynamically as a single step; we propose a method to inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Our additional idea is to consider the effect on the latter part of a circuit carefully by considering the qubit layout when composing an MPMCT gate. We show some experimental results to confirm the effectiveness of our method.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 18, 2021•1 citation

MPMCT gate decomposition method reducing T-depth quickly in proportion to the number of work qubits

Jongheon Lee, Yousung Kang, You-Seok Lee +2 more

Abstract We propose a method for efficient mixed polarity multiple controlled Toffoli (MPMCT) gate decomposition from the perspective of a cost metric related to Toffoli gates, namely Toffoli-depth. When using the technique presented in a previous study, there is a range in which Toffoli-depth (consequently T-depth) of the implemented circuit increases proportionally as the number of provided (clean) work qubits increases. In other words, using the previous technique may result in more inefficient MPMCT gates even though the number of helpful work qubits has increased. In this work, a technique is devised to provide sufficient help from clean work qubits at the central part of the implemented circuit as many as possible, thereby addressing the issues with the previous technique. Meanwhile, one of the representative algorithms that use MPMCT gates is Grover’s algorithm. We show the implementation results for MPMCT gates according to the number of work qubits, using Grover’s algorithm as an example. It is experimentally demonstrated that T-depth decreases much more quickly when using our method than the previous method.

Quantum Information Processing•Oct 17, 2023•6 citations

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

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
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.
Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates are generally used to implement large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that invariably has a physical limitation, which means we need to (1) decompose the MPMCT gates into one- or two-qubit gates, and then (2) insert SWAP gates so that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have only been studied independently. In this work, we investigate that the total number of gates in a circuit can be decreased if the above two processes are considered simultaneously as a single step. We developed a method that inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Also, we consider the effect on the latter part of a circuit carefully by considering the qubit placement when decomposing an MPMCT gate. Experimental results demonstrate the effectiveness of our method.
We usually use Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates to realize large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that has some physical limitation; (1) we need to decompose MPMCT gates into one or two-qubit gates, and then (2) we need to insert SWAP gates such that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have been independently studied intensively. This paper points out that we can decrease the total number of the gates in a circuit if the above two processes are considered dynamically as a single step; we propose a method to inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Our additional idea is to consider the effect on the latter part of a circuit carefully by considering the qubit layout when composing an MPMCT gate. We show some experimental results to confirm the effectiveness of our method.
We usually use Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates to realize large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that has some physical limitation; (1) we need to decompose MPMCT gates into one or two-qubit gates, and then (2) we need to insert SWAP gates such that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have been independently studied intensively. This paper points out that we can decrease the total number of the gates in a circuit if the above two processes are considered dynamically as a single step; we propose a method to inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Our additional idea is to consider the effect on the latter part of a circuit carefully by considering the qubit layout when composing an MPMCT gate. We show some experimental results to confirm the effectiveness of our method.
Abstract We propose a method for efficient mixed polarity multiple controlled Toffoli (MPMCT) gate decomposition from the perspective of a cost metric related to Toffoli gates, namely Toffoli-depth. When using the technique presented in a previous study, there is a range in which Toffoli-depth (consequently T-depth) of the implemented circuit increases proportionally as the number of provided (clean) work qubits increases. In other words, using the previous technique may result in more inefficient MPMCT gates even though the number of helpful work qubits has increased. In this work, a technique is devised to provide sufficient help from clean work qubits at the central part of the implemented circuit as many as possible, thereby addressing the issues with the previous technique. Meanwhile, one of the representative algorithms that use MPMCT gates is Grover’s algorithm. We show the implementation results for MPMCT gates according to the number of work qubits, using Grover’s algorithm as an example. It is experimentally demonstrated that T-depth decreases much more quickly when using our method than the previous method.
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.