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

Design, Automation, and Test in Europe

Dynamic Realization of Multiple Control Toffoli Gate

Abhoy Kole, Arighna Deb, Kamalika Datta, Rolf Drechsler

Published Mar 25, 2024• 6 citations
Publisher

Abstract

Dynamic Quantum Circuits (DQC) is an inevitable solution for today's Noisy Intermediate Scale Quantum (NISQ) systems. This enables realization of an n-qubit (where,$n > 2$) quantum circuit using only 2-qubits with the aid of additional non-unitary operations which is evident from the recent dynamic realizations of algorithms like Quantum Phase Estimation (QPE) and Bernstein- Vazirani (BV) as well as 3-qubit Toffoli operation. In this work, we introduce two different dynamic realization schemes for Multiple Control Toffoli (MCT) gates, for the first time to the best of our knowledge. We compare the respective realizations in terms of resources (e.g., gate, depth and nearest neighbor overhead) and computational accuracy. For this purpose, we apply the proposed dynamic MCT gates in Deutsch-Jozsa (DJ) algorithm, thereby realizing the traditional DJ algorithm as DQCs. Experimental evaluations show that one dynamic scheme for MCT gates leads to DQCs with better computational accuracy, while the other one results in DQCs with better computational resources.

DOI
10.23919/date58400.2024.10546695

Related papers

Extending the Design Space of Dynamic Quantum Circuits for Toffoli based Network

Abhoy Kole, Arighna Deb, Kamalika Datta +1 more

Recent advances in fault tolerant quantum systems allow to perform non-unitary operations like mid-circuit measurement, active reset and classically controlled gate operations in addition to the existing unitary gate operations. Real quantum devices that support these non-unitary operations enable us to execute a new class of quantum circuits, known as Dynamic Quantum Circuits (DQC). This helps to enhance the scalability, thereby allowing execution of quantum circuits comprising of many qubits by using at least two qubits. Recently DQC realizations of multi-qubit Quantum Phase Estimation (QPE) and Bernstein-Vazirani (BV) algorithms have been demonstrated in two separate experiments. However the dynamic transformation of complex quantum circuits consisting of Toffoli gate operations have not been explored yet. This motivates us to: (a) explore the dynamic realization of Toffoli gates by extending the design space of DQC for Toffoli networks, and (b) propose a general dynamic transformation algorithm for the first time to the best of our knowledge. More precisely, we introduce two dynamic transformation schemes (dynamic-1 and dynamic-2) for Toffoli gates, that differ with respect to the required number of classically controlled gate operations. For evaluation, we consider the Deutsch-Jozsa (DJ) algorithm composed of one or more Toffoli gates. Experimental results demonstrate that dynamic DJ circuits based on dynamic-2 Toffoli realization scheme provides better computational accuracy over the dynamic-1 scheme. Further, the proposed dynamic transformation scheme is generic and can also be applied to non-Toffoli quantum circuits, e.g. BV algorithm.

Design, Automation, and Test in Europe•Apr 1, 2023•7 citations

Elementary Quantum Gate Realizations for Multiple-Control Toffoli Gates

D. Michael Miller, Robert Wille, Zahra Sasanian

A new method for determining elementary quantum gate realizations for multiple-control Toffoli (MCT) gates is presented. The realization for each MCT gate is formed as a composition of realizations of smaller MCT gates. A marking algorithm which is more effective than the traditional moving rule is used to optimize the final circuit. The main improvement is that the resulting circuits make significantly better use of ancillary lines than has been achieved in earlier approaches. Initial results are also presented for circuits with nearest-neighbour communication. These results show that the overall approach is not as effective for that problem indicating that research on direct synthesis of nearest-neighbour quantum circuits should be considered. While, the results presented are for the NCV quantum gate library (i.e. for quantum circuits composed of NOT gates, controlled-NOT gates, and controlled-V=V+gates), the approach can be applied to other libraries of elementary quantum gates.

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

Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques

Md. Belayet Ali, Takashi Hirayama, Katsuhisa Yamanaka +1 more

Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.

International Conference on Computational Science and Computational Intelligence (CSCI)•Dec 1, 2015•18 citations

Unlocking the Benefits of Dynamic Quantum Circuits in Resource Constraint Architecture

Abhoy Kole, Mohammed Elkacem Djeridane, Arighna Deb +3 more

The execution of large-scale quantum algorithms is currently constrained by the limited number of available qubits, qubit connectivity restrictions, and the inherent noise in quantum processors. To address these limitations, a design methodology known as Dynamic Quantum Circuits (DQC) has emerged. DQC leverages non-unitary operations-such as active reset, midcircuit measurement, and classically controlled gate operationsto reduce qubit requirements during circuit design. Recently, DQC-based implementations have been explored for various algorithms, including Shor’s Prime Factorization, Quantum Phase Estimation (QPE), and Bernstein-Vazirani (BV), as well as for key operations like state preparation, Toffoli networks, and nonlocal gates. While DQC offers a significant reduction in qubit usage, it introduces a trade-off in the form of increased circuit depth. Therefore, assessing the reliability of such circuits becomes crucial in the context of current quantum hardware architectures. In this paper, we analyze the reliability of DQC-based quantum circuit realizations as a function of qubit count and circuit depth. We present empirical results for two algorithms and evaluate how architectural parameters impact their reliability.

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

Efficient Circuits for Quantum Search over 2D Square Lattice Architecture

Shaohan Hu, Dmitri Maslov, Marco Pistoia +1 more

Quantum computing has increasingly drawn interest and investments from the academic, industrial, and governmental research communities worldwide. Among quantum algorithms, Quantum Search is important for its quadratic speedup over its classical-computing counterpart. A key ingredient in its implementation is the Multi-Control Toffoli (MCT) gate, which creates a Boolean product of control variables and XORs it into the target. On an idealized quantum computer, all-to-all connectivity would eliminate the need to use SWAP gates to communicate information. This is, however, not affordable in the current Noisy Intermediate-Scale Quantum (NISQ) computing era. In this work, we discuss how to efficiently implement MCT gates on 2D Square Lattices (2DSL), suitable for superconducting circuits, by taking advantage of relative-phase Toffoli gates and H-tree layouts to drastically reduce resulting circuits' depths and the amount of SWAPping required.

ACM/IEEE Design Automation Conference (DAC)•May 23, 2019•9 citations
Dynamic Quantum Circuits (DQC) is an inevitable solution for today's Noisy Intermediate Scale Quantum (NISQ) systems. This enables realization of an n-qubit (where,n>2n > 2n>2) quantum circuit using only 2-qubits with the aid of additional non-unitary operations which is evident from the recent dynamic realizations of algorithms like Quantum Phase Estimation (QPE) and Bernstein- Vazirani (BV) as well as 3-qubit Toffoli operation. In this work, we introduce two different dynamic realization schemes for Multiple Control Toffoli (MCT) gates, for the first time to the best of our knowledge. We compare the respective realizations in terms of resources (e.g., gate, depth and nearest neighbor overhead) and computational accuracy. For this purpose, we apply the proposed dynamic MCT gates in Deutsch-Jozsa (DJ) algorithm, thereby realizing the traditional DJ algorithm as DQCs. Experimental evaluations show that one dynamic scheme for MCT gates leads to DQCs with better computational accuracy, while the other one results in DQCs with better computational resources.
Recent advances in fault tolerant quantum systems allow to perform non-unitary operations like mid-circuit measurement, active reset and classically controlled gate operations in addition to the existing unitary gate operations. Real quantum devices that support these non-unitary operations enable us to execute a new class of quantum circuits, known as Dynamic Quantum Circuits (DQC). This helps to enhance the scalability, thereby allowing execution of quantum circuits comprising of many qubits by using at least two qubits. Recently DQC realizations of multi-qubit Quantum Phase Estimation (QPE) and Bernstein-Vazirani (BV) algorithms have been demonstrated in two separate experiments. However the dynamic transformation of complex quantum circuits consisting of Toffoli gate operations have not been explored yet. This motivates us to: (a) explore the dynamic realization of Toffoli gates by extending the design space of DQC for Toffoli networks, and (b) propose a general dynamic transformation algorithm for the first time to the best of our knowledge. More precisely, we introduce two dynamic transformation schemes (dynamic-1 and dynamic-2) for Toffoli gates, that differ with respect to the required number of classically controlled gate operations. For evaluation, we consider the Deutsch-Jozsa (DJ) algorithm composed of one or more Toffoli gates. Experimental results demonstrate that dynamic DJ circuits based on dynamic-2 Toffoli realization scheme provides better computational accuracy over the dynamic-1 scheme. Further, the proposed dynamic transformation scheme is generic and can also be applied to non-Toffoli quantum circuits, e.g. BV algorithm.
A new method for determining elementary quantum gate realizations for multiple-control Toffoli (MCT) gates is presented. The realization for each MCT gate is formed as a composition of realizations of smaller MCT gates. A marking algorithm which is more effective than the traditional moving rule is used to optimize the final circuit. The main improvement is that the resulting circuits make significantly better use of ancillary lines than has been achieved in earlier approaches. Initial results are also presented for circuits with nearest-neighbour communication. These results show that the overall approach is not as effective for that problem indicating that research on direct synthesis of nearest-neighbour quantum circuits should be considered. While, the results presented are for the NCV quantum gate library (i.e. for quantum circuits composed of NOT gates, controlled-NOT gates, and controlled-V=V+gates), the approach can be applied to other libraries of elementary quantum gates.
Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.
The execution of large-scale quantum algorithms is currently constrained by the limited number of available qubits, qubit connectivity restrictions, and the inherent noise in quantum processors. To address these limitations, a design methodology known as Dynamic Quantum Circuits (DQC) has emerged. DQC leverages non-unitary operations-such as active reset, midcircuit measurement, and classically controlled gate operationsto reduce qubit requirements during circuit design. Recently, DQC-based implementations have been explored for various algorithms, including Shor’s Prime Factorization, Quantum Phase Estimation (QPE), and Bernstein-Vazirani (BV), as well as for key operations like state preparation, Toffoli networks, and nonlocal gates. While DQC offers a significant reduction in qubit usage, it introduces a trade-off in the form of increased circuit depth. Therefore, assessing the reliability of such circuits becomes crucial in the context of current quantum hardware architectures. In this paper, we analyze the reliability of DQC-based quantum circuit realizations as a function of qubit count and circuit depth. We present empirical results for two algorithms and evaluate how architectural parameters impact their reliability.
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.
Quantum computing has increasingly drawn interest and investments from the academic, industrial, and governmental research communities worldwide. Among quantum algorithms, Quantum Search is important for its quadratic speedup over its classical-computing counterpart. A key ingredient in its implementation is the Multi-Control Toffoli (MCT) gate, which creates a Boolean product of control variables and XORs it into the target. On an idealized quantum computer, all-to-all connectivity would eliminate the need to use SWAP gates to communicate information. This is, however, not affordable in the current Noisy Intermediate-Scale Quantum (NISQ) computing era. In this work, we discuss how to efficiently implement MCT gates on 2D Square Lattices (2DSL), suitable for superconducting circuits, by taking advantage of relative-phase Toffoli gates and H-tree layouts to drastically reduce resulting circuits' depths and the amount of SWAPping required.