Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.
Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.
Research in Reversible Logic Synthesis is progressing due to its application in quantum computing, low power applications, DNA computing. Reversible computing is efficient in terms of saving power compared to irreversible computing. The work presented here is an attempt to illustrate the shared cube synthesis proposed by N. M. Nayeem et. al with pseudocode. Stepwise demonstration is illustrated with reversible function not considered in the original work. Pseudocode is verified against benchmark reversible functions. The algorithm is experimented on new reversible functions in order to realize quantum diagram, quantum cost, gate count and garbage outputs.
This paper introduces new algorithms to synthesize reversible functions using EXOR-sum of Products-of-EXOR-sums (EPOE) structures. The motivation for using these structures is to reduce the number of as well as the sizes of multiple controlled Toffoli gates, and thus the quantum cost. To achieve these reductions the paper generalizes from existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. Our approach can be applied to reversible and permutative quantum circuits to synthesize single output functions on to an output line, with no additional ancilla bits. A comparison of the ESOP minimizer EXORCISM-4 and two variants of the EPOE minimizer, called EPOEM-1s and EPOEM-2, is presented. The results show that EPOE circuits do in fact achieve the above-stated cost reductions, in particular when expressed in terms of Maslov's quantum cost, the metric commonly used in quantum circuit synthesis.
In this paper a new heuristic ESOP-based synthesis method for Toffoli networks is proposed. This synthesis method takes advantage of the shared-ESOP cubes among the outputs to generate a cascade of Toffoli gates. The method is suitable to generate circuits for functions with large number of input variables. A greedy approach is utilized to select pairs among the different outputs with common ESOP-cubes. The shared terms need only to be realized once and the result can then be transferred to the second output, and thus reducing the number of Toffoli gates. The synthesis algorithm has been applied to a set of benchmark functions. Experimental results show that the algorithm can generate circuits with reduced quantum cost for virtually all functions. Template applications can further improve the results.
Emerging technologies with asymptotic zero power dissipation, such as quantum computing, require the logical operations to be done in a reversible manner. In recent years, the problem of synthesizing Boolean functions in the reversible logic domain has gained significant research attention. The efficiency of the synthesis methods is measured in terms of quantum cost, gate cost, garbage lines, logic depth and speed of synthesis. In this paper, we present an approach based on Exclusive sum-of-Products (ESOP), which allows the user to explore the trade-off between quantum cost and garbage lines. The proposed technique adds a new dimension to the reversible logic synthesis solutions. We demonstrate by detailed experiments that controlled improvement in quantum cost and gate count by increasing garbage count can be achieved. In some cases, improved quantum cost and gate count compared to state-of-the-art synthesis methods are reported. Furthermore, we propose a novel rule-based approach to achieve ancilla-free reversible logic synthesis starting from an ESOP formulation.
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.