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 Circuits, Control, Communication and Computing (I4C)

Post synthesis optimization of reversible logic functions with extended template matching

H. V. Jayashree, V.K. Agrawal, N Shishir Bharadwaj

Published Nov 1, 2014• 1 citation
Publisher

Abstract

Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.

DOI
10.1109/cimca.2014.7057825

Related papers

Quantum cost realization of new reversible gates with transformation based synthesis technique

H. V. Jayashree, V.K. Agrawal, Shishir Bharadwaj N

Reversible computing appears to be promising due its applications in emerging technologies. To compute any reversible function it is necessary to build the system with reversible gates. Simplified version of transformation technique [3,5] to synthesize new reversible gates with Fredkin and Toffoli gates network is presented in this paper. Basic and bidirectional transformation algorithms with an example are illustrated, which uncovers every step of the algorithm. The same example is used for both the algorithms to give clarity on the difference in the efficiency of the algorithms. Simple pseudo code is also presented to illustrate the steps of the algorithm. The best quantum cost obtained is listed in this paper.

IEEE International Conference on VLSI Systems, Architecture, Technology and Applications (VLSI SATA)•Jan 1, 2015•0 citations

Fredkin/Toffoli templates for reversible logic synthesis

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.

International Conference on Computer Aided Design•May 13, 2004•23 citations

A modified Transformation-Template based Synthesis using FREDKIN/SWAP Gates in Reversible Circuits

Mousum Handique, Rijumoni Singha

Reversible logic computing is an emerging research area due to its high-speed computing abilities and generating the lossless information. Due to the ability of reverse operation and high-speed computing performance, reversible computation is considered as a future alternative to the conventional computing. The rapid progress of reversible computation in the current scenario, the reversible circuit is the way to solve this type of computation. Moreover, the reversible circuit computation is the higher level abstraction of the quantum circuit. The synthesis design of these circuits is an important aspect in the current literature. In this paper, we present our work in the field of synthesis design of a reversible circuit. In this work, we propose a modified transformation-based synthesis design using the FREDKIN/SWAP gate to reduce the quantum cost and minimizing the number of gates. To obtain this synthesis design approach, we have introduced some new templates which are defined by rules of replacing the k-CNOT/FREDKIN/SWAP gates using a template matching approach. Here, we are considering only k-CNOT ( k ≥ 1), FREDKIN and SWAP based gate in our templates. Finally, we provide our experimental results based on different benchmark reversible circuits. The experimental result has shown that the number of quantum cost and gate count are reduced using the FREDKIN/SWAP gate in the transformation-based approach with the help of proposed templates.

Procedia Computer Science•Jan 1, 2018•2 citations

Reversible circuit optimization using modified toffoli templates

Mridula J Deshpande, H. V. Jayashree, V.K. Agrawal

Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.

International Conference on Advances in Computing, Communications and Informatics (ICACCI)•Sep 1, 2017•0 citations

Toffoli network synthesis with templates

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 24, 2005•228 citations

Fredkin-Enabled Transformation-Based Reversible Logic Synthesis

Mathias Soeken, Anupam Chattopadhyay

Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being quantum computing. The problem of implementing a given Boolean function using a set of elementary reversible logic gates is known as reversible logic synthesis. Due to the presumed hardness of the reversible circuit synthesis problem, different heuristics have been proposed in the literature to reduce quantum cost (QC), gate count, and logical depth without using ancillary lines. Interestingly, none of these heuristics systematically utilize Fredkin gates. In this paper, we demonstrate, both theoretically and empirically, that accommodating Fredkin gates significantly improves the performance of reversible circuits.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2015•13 citations
Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.
Reversible computing appears to be promising due its applications in emerging technologies. To compute any reversible function it is necessary to build the system with reversible gates. Simplified version of transformation technique [3,5] to synthesize new reversible gates with Fredkin and Toffoli gates network is presented in this paper. Basic and bidirectional transformation algorithms with an example are illustrated, which uncovers every step of the algorithm. The same example is used for both the algorithms to give clarity on the difference in the efficiency of the algorithms. Simple pseudo code is also presented to illustrate the steps of the algorithm. The best quantum cost obtained is listed in this paper.
Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.
Reversible logic computing is an emerging research area due to its high-speed computing abilities and generating the lossless information. Due to the ability of reverse operation and high-speed computing performance, reversible computation is considered as a future alternative to the conventional computing. The rapid progress of reversible computation in the current scenario, the reversible circuit is the way to solve this type of computation. Moreover, the reversible circuit computation is the higher level abstraction of the quantum circuit. The synthesis design of these circuits is an important aspect in the current literature. In this paper, we present our work in the field of synthesis design of a reversible circuit. In this work, we propose a modified transformation-based synthesis design using the FREDKIN/SWAP gate to reduce the quantum cost and minimizing the number of gates. To obtain this synthesis design approach, we have introduced some new templates which are defined by rules of replacing the k-CNOT/FREDKIN/SWAP gates using a template matching approach. Here, we are considering only k-CNOT ( k ≥ 1), FREDKIN and SWAP based gate in our templates. Finally, we provide our experimental results based on different benchmark reversible circuits. The experimental result has shown that the number of quantum cost and gate count are reduced using the FREDKIN/SWAP gate in the transformation-based approach with the help of proposed templates.
Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.
Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being quantum computing. The problem of implementing a given Boolean function using a set of elementary reversible logic gates is known as reversible logic synthesis. Due to the presumed hardness of the reversible circuit synthesis problem, different heuristics have been proposed in the literature to reduce quantum cost (QC), gate count, and logical depth without using ancillary lines. Interestingly, none of these heuristics systematically utilize Fredkin gates. In this paper, we demonstrate, both theoretically and empirically, that accommodating Fredkin gates significantly improves the performance of reversible circuits.