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.
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.
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.
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 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.
Summary form only given, as follows. With the increasing emphasis on low-power design and quantum computation, research activities in the area of reversible logic synthesis and testing have gained momentum over the last couple of decades. It is expected that reversible logic will provide us with a viable alternative to building ultra-low power circuits and systems in not too distant future. In the classical works for synthesis of reversible circuits, gate libraries comprising of standard reversible gates like NOT, CNOT, TOFFOLI, FREDKIN, etc. are considered. To evaluate the goodness of a synthesized netlist, various metrics such as gate count, quantum cost, and equivalent transistor cost have been considered by various researchers. The synthesis approaches that have been reported can be broadly categorized into three groups: (a) exact synthesis approaches which try to obtain optimal reversible gate netlists, but can be used for small circuits only, (b) heuristic based approaches which try to utilize some domain knowledge intelligently to reduce the complexity of search, and can be used for somewhat larger circuits, and (c) synthesis approaches that rely on higher level functional representations like binary decision diagram (BDD) or exclusive sum-ofproducts (ESOP). The last approach is scalable to larger circuits (with 200 inputs or more), however, the synthesized netlist is not optimal and various rule-based heuristic approaches have been proposed to minimize the cost. There have been works also that report techniques for implementing sequential circuits with reversible properties, which will be useful for building complex systems containing finite-state machines. There are various transformations that are carried out as part of cryptographic algorithms that are inherently reversible in nature. For instance, any block cipher that uses a key K to transform a plaintext P into a ciphertext C during encryption must be reversible, because decryption will be doing just the reverse (C to P). Also, in standard symmetric block ciphers like DES or AES, there is a combinational block called substitution box or S-box which is also reversible in nature. In AES, the S-box has 8 inputs and 8 outputs, and implements a one-to-one onto mapping. The same reversibility requirements hold for stream ciphers and public-key ciphers like RSA. Although not much work has been carried out in the area of reversible implementations of cryptographic algorithms, this can be a very good area for future research. Similar considerations hold for various coding and decoding techniques used in communication, which are also inherently reversible in nature. Some examples of such coding/decoding are Manchester, Differential Manchester, Bipolar AMI, 4B/5B, 8B/10B, Hamming error correcting code, etc. All these techniques can potentially be implemented using reversible logic circuits. Specific case studies of some of the areas as mentioned will be reported, with synthesis results.
Increasing miniaturization and demand of low power electronics is highly motivating research on reversible logic. Reversible logic has attracted signification attention in fields of Low power VLSI design, computer graphics, quantum computing and communication. A lot of work has been done on synthesis and optimization of reversible circuits followed by quantitative analysis on various optimization metrics like ancillary inputs, garbage outputs and quantum cost. It is therefore obvious to present a quick guide on reversible logic implementation to bridge gap between theory and implementation. Taxonomy diagrams of work done in reversible logic domain are also presented to give a quick review of all about reversible logic. Quantum realization of popular reversible Fredkin gates using RCViewer tool is also presented which will be stepping stone for a new researcher to synthesize and optimize any complex reversible logic based circuit.