We present new algorithms to synthesize exact universal reversible gate library for various types of gates and costs. We use the powerful algebraic software GAP for implementation and examination of our algorithms and the reversible logic synthesis problems have been reduced to group theory problems. It is shown that minimization of arbitrary cost functions of gates and orders of magnitude are faster than its previously counterparts for reversible logic synthesis. Experimental results show that a significant improvement over the previously proposed synthesis algorithm is obtained compared with the existing approaches to reversible logic synthesis.
We present new algorithms to synthesize exact universal reversible gate library for various types of gates and costs. We use the powerful algebraic software GAP for implementation and examination of our algorithms and the reversible logic synthesis problems have been reduced to group theory problems. It is shown that minimization of arbitrary cost functions of gates and orders of magnitude are faster than its previously counterparts for reversible logic synthesis. Experimental results show that a significant improvement over the previously proposed synthesis algorithm is obtained compared with the existing approaches to reversible logic synthesis.
We present new algorithms to synthesize exact universal reversible gate library for various types of gates and costs. We use the powerful algebraic software GAP for implementation and examination of our algorithms and the reversible logic synthesis problems have been reduced to group theory problems. It is shown that minimization of arbitrary cost functions of gates and orders of magnitude are faster than its previously counterparts for reversible logic synthesis. Experimental results show that a significant improvement over the previously proposed synthesis algorithm is obtained compared with the existing approaches to reversible logic synthesis.
We present fast algorithms to synthesize exact minimal reversible circuits for various types of gates and costs. By reducing reversible logic synthesis problems to group theory problems, we use the powerful algebraic software GAP to solve such problems. Our algorithms are not only able to minimize for arbitrary cost functions of gates, but also orders of magnitude faster than the existing approaches to reversible logic synthesis. In addition, we show that the Peres gate is a better choice than the standard Toffoli gate in libraries of universal reversible gates.
Two questions have been addressed here: how many logic levels are necessary to synthesise a specific instance of a reversible circuit, and how much better to have large gate libraries, and what gates should be required in libraries. Group theory is applied to 3-bit reversible gate synthesis to create a library useful in hierarchical design. It has been shown that arbitrary 3-bit reversible circuit can be synthesised with four-logic levels, using this new gate library. The respective universal library for the four-level synthesis is constructed and optimised it on the level of nuclear magnetic resonance pulses. A very fast algorithm to synthesise arbitrary 3-bit reversible function to gates from our library is also presented. The algorithm demonstrates dramatic speed benefit and results in a maximum of four-level circuit for arbitrary 3-bit reversible function. The gates are optimised on the level of pulses to decrease their cost and allow for objective comparison with standard CNOT, NOT, Toffoli gates (CNT) circuits. This library guarantees a four-level circuit for any 3-qubit reversible function and is also intended to be used in a hierarchical design of larger circuits.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.