Reversible logic circuits have been historically motivated by theoretical research in low-power electronics as well as practical improvement of bit manipulation transforms in cryptography and computer graphics. Recently, reversible circuits have attracted interest as components of quantum algorithms, as well as in photonic and nano-computing technologies where some switching devices offer no signal gain. Research in generating reversible logic distinguishes between circuit synthesis, postsynthesis optimization, and technology mapping. In this survey, we review algorithmic paradigms—search based, cycle based, transformation based, and BDD based—as well as specific algorithms for reversible synthesis, both exact and heuristic. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.
Reversible logic circuits have been historically motivated by theoretical research in low-power electronics as well as practical improvement of bit manipulation transforms in cryptography and computer graphics. Recently, reversible circuits have attracted interest as components of quantum algorithms, as well as in photonic and nano-computing technologies where some switching devices offer no signal gain. Research in generating reversible logic distinguishes between circuit synthesis, postsynthesis optimization, and technology mapping. In this survey, we review algorithmic paradigms—search based, cycle based, transformation based, and BDD based—as well as specific algorithms for reversible synthesis, both exact and heuristic. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.
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.
Quantum information processing is of interest as it offers the potential for a new generation of very powerful computers supporting novel computational paradigms. Over the last couple of decades, different aspects of quantum computers ranging from quantum algorithms to quantum physical design have received growing attention. One of the most important research areas is the synthesis and post-synthesis optimization of reversible and quantum circuits. Many synthesis and optimization approaches can be found in the literature, yet, due to the complexity of the problem, finding approaches leading to optimal, or near optimal, results is still an open problem. The synthesized circuits are usually evaluated based on quantum cost models. Therefore, they are often technology mapped to circuits of more primitive gates. To this end, various technology mapping approaches have also been proposed in the past few years. Related work shows an existing gap in optimized technology mapping for reversible and quantum circuits. In this dissertation, an optimized technology mapping design flow is introduced for mapping reversible circuits to quantum circuits. The contributions of this dissertation are classified as follows: - New reversible circuit optimization methods. - Optimized reversible to quantum mapping approaches. - New quantum gate libraries and new cost models for reversible gates based on the new libraries. - Quantum circuit optimization approaches. The steps above, form an optimized flow for mapping reversible circuits to quantum circuits. At each step of the design flow optimized and consistent approaches are suggested with the goal of reducing the quantum cost of the synthesized reversible circuits. The evaluations show that the proposed mapping methodology leads to significant improvement in the quantum cost of the existing benchmark circuits.