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 Computers and Devices for Communication

Group theory based reversible logic synthesis

Kamalika Datta, Indranil Sengupta, Hafizur Rahaman

Published Dec 1, 2012• 5 citations
Publisher

Abstract

With increase in emphasis on low-power design and quantum computation, research in reversible logic synthesis has gained great attention. Various methods of synthesis exist in the literature, like exact synthesis, heuristic approaches, methods based on group theory, and those based on higher level representation of functions like Binary Decision Diagram (BDD). In this paper a group theory based synthesis approach for reversible circuits is presented, using both positive-control and negative-control Toffoli gates. The method uses group theoretic rules for factoring permutation cycles for synthesis. The use of both positive and negative control Toffoli gates results in reduction of total number of gates required as compared to previous methods based on group theory. Several worked out examples illustrate the advantage of the proposed approach.

DOI
10.1109/codec.2012.6509346

Related papers

BDD-Based Synthesis of Reversible Logic

Robert Wille, Rolf Drechsler

Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.

International Journal of Applied Metaheuristic Computing•Oct 1, 2010•8 citations

Reversible Logic Synthesis of Networks of Positive/Negative Control Gates

Wenying Zhu, Zhijin Guan, Yueqing Hang

The research in reversible logic has been attracted in recent years. It has applications in quantum computing, low-power CMOS design and nanotechnology. Many methods on how to cascade a reversible network have been proposed. And all these networks are composed of Toffoli/Fredkin gates. In this paper, we present a method that synthesizes a network with family of Positive/Negative Control (PNC) gates. Through introducing some examples for 3×3 reversible functions, and comparing with the network which is composed of Toffoli gates, the results show that introducing the PNC gates can produce an improvement for the number of gates in the reversible network, and have an advantage in reducing the cost of network.

International Conference on Natural Computation (ICNC)•Jan 1, 2009•2 citations

Positive Davio-based synthesis algorithm for reversible logic

Yu Pang, Shaoquan Wang, Zhilong He +3 more

Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Oct 1, 2011•17 citations

Performance trade-off in decision diagram based synthesis of reversible logic circuits

H. V. Jayashree, Anmol Prakash Surhonne, V.K. Agrawal

Reversible computing is an emerging and promising technique due to its wide applications in quantum, optical and DNA computing and many more. Reversible circuit synthesis is a main focus for researchers as conventional synthesis techniques are not suitable for reversible circuits. Our work focuses on BDD based synthesis as it has capabilities of realizing circuit for large boolean functions unlike other reversible synthesis methods. Existing BDD based synthesis techniques rely on positive [1] and negative [2] controlled Toffoli gates. In this paper work we explore BDD based synthesis technique along with evolutionary computation method. We employed Fredkin and elementary CNOT gate library. Experimental results demonstrate that this approach reduces the gate count and quantum cost at the cost of increase in the number of lines.

IEEE International Conference on Electron Devices and Solid-State Circuits (EDSSC)•Jun 1, 2015•1 citation

Improved Ternary Reversible Logic Synthesis Using Group Theoretic Approach

P. Mercy Nesa Rani, Kamalika Datta

Quantum computation relies on exploiting quantum mechanical phenomena, and has received significant attention in recent years. Higher-dimensional quantum systems increase the density of encoded information per computing element (e.g., qutrit for three-level system), resulting in less resource overhead. For instance, 63% reduction in the number of qutrits is possible for ternary quantum systems as compared to the corresponding binary systems. The proposed work exploits this fact to synthesize ternary reversible circuits employing a cycle-based technique. The method starts from the ternary reversible specification of a given function in the form of a permutation. The permutation cycles are factored into simpler three-cycles and two-cycles, which are then mapped to ternary reversible gates. Different gate libraries are used to synthesize three-cycles and two-cycles, respectively. A gate decomposition approach is also proposed to synthesize a quantum gate netlist in terms of elementary ternary quantum gates, viz. Muthukrishnan–Stroud gate and shift gate. Synthesis results on benchmark functions indicate that the proposed method results in 27% and 6% improvements in quantum cost and gate count, respectively, over existing works in the literature.

Journal of Circuits Systems and Computers•Dec 23, 2019•7 citations

Synthesis of Reversible and Quantum Circuit Using ROCBDD and Mixed-Polarity Toffoli Gate

Hieu Nguyen, Linh Hoang Tran

In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.

IEEE Access•Jan 1, 2021•5 citations
With increase in emphasis on low-power design and quantum computation, research in reversible logic synthesis has gained great attention. Various methods of synthesis exist in the literature, like exact synthesis, heuristic approaches, methods based on group theory, and those based on higher level representation of functions like Binary Decision Diagram (BDD). In this paper a group theory based synthesis approach for reversible circuits is presented, using both positive-control and negative-control Toffoli gates. The method uses group theoretic rules for factoring permutation cycles for synthesis. The use of both positive and negative control Toffoli gates results in reduction of total number of gates required as compared to previous methods based on group theory. Several worked out examples illustrate the advantage of the proposed approach.
Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.
The research in reversible logic has been attracted in recent years. It has applications in quantum computing, low-power CMOS design and nanotechnology. Many methods on how to cascade a reversible network have been proposed. And all these networks are composed of Toffoli/Fredkin gates. In this paper, we present a method that synthesizes a network with family of Positive/Negative Control (PNC) gates. Through introducing some examples for 3×3 reversible functions, and comparing with the network which is composed of Toffoli gates, the results show that introducing the PNC gates can produce an improvement for the number of gates in the reversible network, and have an advantage in reducing the cost of network.
Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.
Reversible computing is an emerging and promising technique due to its wide applications in quantum, optical and DNA computing and many more. Reversible circuit synthesis is a main focus for researchers as conventional synthesis techniques are not suitable for reversible circuits. Our work focuses on BDD based synthesis as it has capabilities of realizing circuit for large boolean functions unlike other reversible synthesis methods. Existing BDD based synthesis techniques rely on positive [1] and negative [2] controlled Toffoli gates. In this paper work we explore BDD based synthesis technique along with evolutionary computation method. We employed Fredkin and elementary CNOT gate library. Experimental results demonstrate that this approach reduces the gate count and quantum cost at the cost of increase in the number of lines.
Quantum computation relies on exploiting quantum mechanical phenomena, and has received significant attention in recent years. Higher-dimensional quantum systems increase the density of encoded information per computing element (e.g., qutrit for three-level system), resulting in less resource overhead. For instance, 63% reduction in the number of qutrits is possible for ternary quantum systems as compared to the corresponding binary systems. The proposed work exploits this fact to synthesize ternary reversible circuits employing a cycle-based technique. The method starts from the ternary reversible specification of a given function in the form of a permutation. The permutation cycles are factored into simpler three-cycles and two-cycles, which are then mapped to ternary reversible gates. Different gate libraries are used to synthesize three-cycles and two-cycles, respectively. A gate decomposition approach is also proposed to synthesize a quantum gate netlist in terms of elementary ternary quantum gates, viz. Muthukrishnan–Stroud gate and shift gate. Synthesis results on benchmark functions indicate that the proposed method results in 27% and 6% improvements in quantum cost and gate count, respectively, over existing works in the literature.
In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.