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

Procedia Computer Science

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

Mousum Handique, Rijumoni Singha

Published Jan 1, 2018• 2 citations
Publisher

Abstract

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.

DOI
10.1016/j.procs.2017.12.102

Related papers

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

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

Post synthesis optimization of reversible logic functions with extended template matching

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

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.

International Conference on Circuits, Control, Communication and Computing (I4C)•Nov 1, 2014•1 citation

Reversible logic synthesis with Fredkin and Peres gates

James Donald, Niraj Kumar Jha

Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis tool, to include additional gate types. While classic RMRLS can synthesize functions using NOT, CNOT, and n -bit Toffoli gates, our work details the inclusion of n -bit Fredkin and Peres gates. We find that these additional gates reduce the average gate count for three-variable functions from 6.10 to 4.56, and improve the synthesis results of many larger functions, both in terms of gate count and quantum cost.

ACM Journal on Emerging Technologies in Computing Systems•Mar 1, 2008•85 citations

Quantum Circuit Simplification Using Templates

D. Maslov, Cho Eun Young, D. Michael Miller +1 more

Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible quantum circuit simplification. We consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.

Design, Automation, and Test in Europe•Apr 1, 2005•120 citations

Design of logic gates using reversible gates with reduced quantum cost

S.Saniya Samrin, Rachamma Patil, Sumangala Itagi +2 more

Reversible logic is also called information lossless logic, since the information embedded in the circuits can be recovered, if lost. Research carried out by Landauer and Bennett proved that the energy dissipation would not occur if computation is made reversible. With this aim a number of reversible gates were designed and invented. As examples like- the Fredkin gate, the Toffoli gate, the Peres gate, and the Feynman gate. Reversible logic has extensive applications and is considered as one of the futuristic technologies. But the logic circuit designing is based on logic gates, which are non-reversible. This paper presents design of logic gates using reversible gates. These logic gates help in future implementation of higher end circuits. In this paper an attempt is made to design logic gates using reversible gates and some of the higher end circuits are also designed such as Binary-to-Grey, grey-to-Binary, Adder, Subtractor etc.

Global Transitions Proceedings•Apr 2, 2022•27 citations
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 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 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.
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 logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis tool, to include additional gate types. While classic RMRLS can synthesize functions using NOT, CNOT, and n -bit Toffoli gates, our work details the inclusion of n -bit Fredkin and Peres gates. We find that these additional gates reduce the average gate count for three-variable functions from 6.10 to 4.56, and improve the synthesis results of many larger functions, both in terms of gate count and quantum cost.
Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible quantum circuit simplification. We consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.
Reversible logic is also called information lossless logic, since the information embedded in the circuits can be recovered, if lost. Research carried out by Landauer and Bennett proved that the energy dissipation would not occur if computation is made reversible. With this aim a number of reversible gates were designed and invented. As examples like- the Fredkin gate, the Toffoli gate, the Peres gate, and the Feynman gate. Reversible logic has extensive applications and is considered as one of the futuristic technologies. But the logic circuit designing is based on logic gates, which are non-reversible. This paper presents design of logic gates using reversible gates. These logic gates help in future implementation of higher end circuits. In this paper an attempt is made to design logic gates using reversible gates and some of the higher end circuits are also designed such as Binary-to-Grey, grey-to-Binary, Adder, Subtractor etc.