Fredkin/Toffoli Templates for Reversible Logic Synthesis
Dmitri Maslov, Gerhard W. Dueck, David Michael Miller · 2003
Abstract—Reversible logic has applications in quantum com-puting, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate (which performs a controlled NOT) and the Fredkin gate (performs a controlled swap of two inputs). Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply trans-formations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified—they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously. I.