Exact Synthesis of Reversible Logic

Abhoy Kole, P. Mercy Nesa Rani, Kamalika Datta +2 more

Realization of logic functions using ternary reversible logic is known to requirelesser number of lines as compared to conventionalbinary reversible logic. This aspect of ternary reversible logic has motivated researchers to explore various synthesis approaches in the past. Existing synthesis methods require additional lines (called ancilla lines)for synthesis, which is expensive from the quantum implementation pointof view. There is no reported work for ternary reversible logic synthesisthat require the minimum possible number of gates and also lines. Thisclass of synthesis methods is called exact synthesis. In this paper two exact synthesis methods for ternary reversible logic have been proposed for the first time, one based on booleansatisfiability (SAT) and the other based on level-constrained heuristic search technique. A permutation representing a reversible ternary truth table is given as input, and a reversible circuit consisting ofgeneralized ternary Toffoli gates that implements the permutationis obtained as output. Experimental studies have been carried out on various randomly generatedternary reversible functions.

Md. Mazder Rahman

Rongliang Fu, Olivia Chen, Nobuyuki Yoshikawa +1 more

Reversible computing, deriving its inspiration from Landauer's principle, has captured significant interest as a promising technology for logic operations without energy dissipation. The reversible quantum-flux-parametron (RQFP) stands as the first practical reversible logic gate using adiabatic superconducting devices, whose logical and physical reversibility has been experimentally demonstrated. However, due to its unique logic function and structure, the design of RQFP logic circuits is a highly challenging task. At present, there are no automated design tools available for RQFP logic. Therefore, this paper proposes the first exact logic synthesis algorithm for RQFP logic. It formulates the synthesis problem as the Boolean satisfiability problem and subsequently constructs and calls upon the incremental propositional logic model iteratively for optimal synthesis with the least number of gates and garbage outputs. Experimental results on the reversible logic benchmark from RevLib demonstrate the effectiveness of the proposed algorithm.

Anas N. Al‐Rabadi

Robert Wille, Daniel J. Grosse

The research in the field of reversible logic is motivated by its application in low-power design, optical computing and quantum computing. Hence synthesis of reversible logic has become a very important research area in the last years. In this paper exact algorithms for the synthesis of generalized Toffoli networks are considered. We present an improvement of an existing synthesis approach that is based on Boolean Satisfiability. Furthermore, the principle limits of the original and the improved approach are shown. Then, we propose a new method using problem specific knowledge during the synthesis process to overcome these limits. Experimental results demonstrate improvements of the overall synthesis time up to four orders of magnitude.

Robert Wille, Rolf Drechsler