Article Preview
Top1. Introduction
Reversible logic (Landauer, 1961; Bennett, 1973; Toffoli, 1980) realizes n-input n-output functions that map each possible input vector to a unique output vector (i.e., bijections). Although reversible logic significantly differs from traditional (irreversible) logic (e.g., fan-out and feedback are not allowed), it has become an intensely studied research area in recent years. In particular, this is caused by the fact that reversible logic is the basis for several emerging technologies, while traditional methods suffer from the increasing miniaturization and the exponential growth of the number of transistors in integrated circuits. Researchers expect that in 10-20 years duplication of transistor density every 18 months (according to Moore’s Law) is not possible any longer (Zhirnov, Cavin, Hutchby, & Bourianoff, 2003). Then, alternatives are needed. Reversible logic offers such alternatives as the following applications show:
Further applications of reversible logic can be found in the domain of optical computing (Cuykendall & Andersen, 1987), DNA computing (Bennett, 1973), and nanotechnologies (Merkle, 1993).
However, currently the synthesis of reversible or quantum circuits, respectively, is limited. Exact (Hung, Song, Yang, Yang & Perkowski, 2006; Große, Wille, Dueck & Drechsler, 2009) as well as heuristic (Shende, Prasad, Markov & Hayes, 2003; Miller, Maslov & Dueck, 2003; Kerntopf, 2004; Maslov, Dueck & Miller, 2005, 2007; Gupta, Agrawal, & Jha, 2006) methods have been proposed. But both are applicable only for relatively small functions. Exact approaches reach their limits with functions containing more than 6 variables (Große, Wille, Dueck & Drechsler, 2009) while heuristic methods are able to synthesize functions with at most 30 variables (Gupta, Agrawal, & Jha, 2006). Moreover, often a significant amount of run-time is needed to achieve these results.