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

International Conference on VLSI Design

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

Laxmidhar Biswal, Chandan Bandyopadhyay, Robert Wille, Rolf Drechsler, Hafizur Rahaman

Published Jan 1, 2016• 10 citations
Publisher

Abstract

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.

DOI
10.1109/vlsid.2016.23

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

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

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

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

Optimizing the Mapping of Reversible Circuits to Four-Valued Quantum Gate Circuits

Mathias Soeken, Zahra Sasanian, Robert Wille +2 more

This paper considers the optimization of reversible circuits composed of multiple-control Toffoli gates to quantum circuits using the well-known NCV-1 (NCV) library and the recently introduced NCV-v1 library which both use a four-valued model for the quantum gates. The techniques introduced handle positive and negative controls which are central to many reversible circuit synthesis procedures. Experimental results confirm the methods are applicable to circuits obtained by diverse synthesis methods. The results also show the significant advantage of the NCV-v1 library.

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

Recent Developments on Mapping Reversible Circuits to Quantum Gate Libraries

D. Michael Miller, Zahra Sasanian

This paper reviews recent developments on mapping reversible circuits to libraries of elementary quantum gates. The emphasis is on optimization of both the initial reversible circuit and the resulting quantum circuit. At the quantum level, improved realizations of single mixed-polarity multiple-control Toffoli gates are presented as well as techniques for performing quantum gate optimizations across Toffoli gate boundaries. Experimental results show the effectiveness of the methods presented using circuits from the REVLIB benchmark suite.

International Symposium on Electronic System Design•Dec 1, 2012•7 citations
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.
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.
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.
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.
This paper considers the optimization of reversible circuits composed of multiple-control Toffoli gates to quantum circuits using the well-known NCV-1 (NCV) library and the recently introduced NCV-v1 library which both use a four-valued model for the quantum gates. The techniques introduced handle positive and negative controls which are central to many reversible circuit synthesis procedures. Experimental results confirm the methods are applicable to circuits obtained by diverse synthesis methods. The results also show the significant advantage of the NCV-v1 library.
This paper reviews recent developments on mapping reversible circuits to libraries of elementary quantum gates. The emphasis is on optimization of both the initial reversible circuit and the resulting quantum circuit. At the quantum level, improved realizations of single mixed-polarity multiple-control Toffoli gates are presented as well as techniques for performing quantum gate optimizations across Toffoli gate boundaries. Experimental results show the effectiveness of the methods presented using circuits from the REVLIB benchmark suite.