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)

Elementary Quantum Gate Realizations for Multiple-Control Toffoli Gates

D. Michael Miller, Robert Wille, Zahra Sasanian

Published May 1, 2011• 141 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl.2011.54

Related papers

NCV realization of MCT gates with mixed controls

Zahra Sasanian, D. Michael Miller

Multiple-control Toffoli (MCT) gates are widely used in the synthesis of reversible circuits. These gates are not usually directly implemented and need to be mapped to circuits of more elementary components such as quantum gates. In this work, the realization of MCT gates with mixed controls is explored for the NCV quantum library containing NOT, CNOT, V and V+gates. The results show that the proposed approach significantly improves the best known NCV costs for MCT gates.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)•Aug 1, 2011•18 citations

Improving the Realization of Multiple-Control Toffoli Gates Using the NCVW Quantum Gate Library

Laxmidhar Biswal, Chandan Bandyopadhyay, Robert Wille +2 more

Multiple Control Toffoli (MCT) gates are the main constituent of reversible circuits. For quantum circuits, MCT gates are realized using quantum gate libraries such as NCV or NCVW which are composed of universal quantum gates like NOT, CNOT, V/V+, and W/W+. In order to improve the design of quantum circuits, the mapping of MCT gates to a cascade of these quantum gates has to be improved as well. In this work, we propose reconfigured structures of quantum gates realizing MCT gates. To this end, we rely on the established mapping structure, but append redundant gates which can be used afterwards for simplifications. Eventually, the proposed design is mapped to an NCVW quantum circuit. We have successfully tested our mapping technique. The obtained results have experimentally been compared to related work.

International Conference on VLSI Design•Jan 1, 2016•10 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

Improved NCV Gate Realization of Arbitrary Size Toffoli Gates

Abhoy Kole, Kamalika Datta

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.

International Conference on VLSI Design•Jan 1, 2017•11 citations

Lower cost quantum gate realizations of multiple-control Toffoli gates

D. Michael Miller

A systematic method is presented for realizing multiple-control Toffoli gates using elementary quantum gates. Results are presented showing that for the NOT, controlled-NOT and the two square root of NOT gates, the method produces circuits as good and in certain cases better than those known to date. A major feature of the work reported here is that in addition to the previously studied cases of one and the maximum required ancillary lines, the presented method covers all cases in between. The approach is general and can be directly applied to other sets of elementary gates.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)•Aug 1, 2009•15 citations

Layout Synthesis for Quantum Circuits Considering Toffoli Gate Decomposition

Po-Wei Chen, Sheng-Tan Huang, Shao‐Yun Fang

State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.

ACM Transactions on Design Automation of Electronic Systems•Jun 16, 2025•1 citation
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.
Multiple Control Toffoli (MCT) gates are the main constituent of reversible circuits. For quantum circuits, MCT gates are realized using quantum gate libraries such as NCV or NCVW which are composed of universal quantum gates like NOT, CNOT, V/V+, and W/W+. In order to improve the design of quantum circuits, the mapping of MCT gates to a cascade of these quantum gates has to be improved as well. In this work, we propose reconfigured structures of quantum gates realizing MCT gates. To this end, we rely on the established mapping structure, but append redundant gates which can be used afterwards for simplifications. Eventually, the proposed design is mapped to an NCVW quantum circuit. We have successfully tested our mapping technique. The obtained results have experimentally been compared to related work.
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 problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.
A systematic method is presented for realizing multiple-control Toffoli gates using elementary quantum gates. Results are presented showing that for the NOT, controlled-NOT and the two square root of NOT gates, the method produces circuits as good and in certain cases better than those known to date. A major feature of the work reported here is that in addition to the previously studied cases of one and the maximum required ancillary lines, the presented method covers all cases in between. The approach is general and can be directly applied to other sets of elementary gates.
State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.