Transformation-based synthesis is a well established systematic approach to determine a circuit implementation from a reversible function specification. Due to the inherent bidirectionality of reversible circuits the basic method can be applied in a bidirectional manner. In the approaches to date, gates are added either to the input side or the output side of the circuit on each iteration. I n this paper, we introduce a new variation where gates may be added at both ends during a single iteration when this is advantageous to reducing the cost of the circuit. Experimental results show the advantage of the new approach over previous transformation-based synthesis methods and that the additional computation is justified by the possibility of improved circuit costs.
Transformation-based synthesis is a well established systematic approach to determine a circuit implementation from a reversible function specification. Due to the inherent bidirectionality of reversible circuits the basic method can be applied in a bidirectional manner. In the approaches to date, gates are added either to the input side or the output side of the circuit on each iteration. I n this paper, we introduce a new variation where gates may be added at both ends during a single iteration when this is advantageous to reducing the cost of the circuit. Experimental results show the advantage of the new approach over previous transformation-based synthesis methods and that the additional computation is justified by the possibility of improved circuit costs.
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.
An important property of reversible circuits is that they can reduce the energy consumption which is now a big problem for the advanced circuit design. If a circuit is reversible, it can reduce the energy consumption caused by information loss. The tabulation method is more efficient than other simplification methods for combination logic circuits. But the classical tabulation method is not directly applicable to reversible circuits because the basic logic gates, except the NOT gate, are not reversible gates. In this paper, we propose a method to solve the problem so that the tabulation method can be applied to the reversible circuit synthesis. Our algorithm provides a systematic method to simplify the reversible circuit. This can produce the resulting expression in exclusive-sum form and transform it into a final reversible circuit with lower quantum cost. Moreover, we can realize permutations to be reversible circuits with lower quantum cost and without unnecessary garbage bits. We can also convert irreversible circuits by adding qubits to make the circuits reversible. The experimental results show that the average saving in quantum cost is 15.82% compared with previous approaches.
In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.
Reversible computing appears to be promising due its applications in emerging technologies. To compute any reversible function it is necessary to build the system with reversible gates. Simplified version of transformation technique [3,5] to synthesize new reversible gates with Fredkin and Toffoli gates network is presented in this paper. Basic and bidirectional transformation algorithms with an example are illustrated, which uncovers every step of the algorithm. The same example is used for both the algorithms to give clarity on the difference in the efficiency of the algorithms. Simple pseudo code is also presented to illustrate the steps of the algorithm. The best quantum cost obtained is listed in this paper.
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.
Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis method.