A transformation based algorithm for reversible logic synthesis

A digital combinational logic circuit is reversible if it maps each input pattern to a unique output pattern. Such circuits are of interest in quantum computing, optical computing, nanotechnology and low-power CMOS design. Synthesis ap-proaches are not well developed for reversible circuits even for small numbers of inputs and outputs. In this paper, a transformation based algorithm for the synthesis of such a reversible circuit in terms of n n Tof-foli gates is presented. Initially, a circuit is constructed by a single pass through the specication with minimal look-ahead and no back-tracking. Reduction rules are then ap-plied by simple template matching. The method produces near-optimal results for 3-input circuits and also produces very good results for larger problems