Asymptotically Optimal Regular Synthesis of Reversible Logic Networks
Dmitri A Maslov, Gerhard W. Dueck · 2003
We propose a network of generalized Tooli gates with mul-tiple EXORs for the realization of reversible functions. If implemented as a quantum circuit, the cost of such gates is shown to be only marginally higher than the cost of a Tooli gate with a single EXOR and the same number of controls. The main result is a regular synthesis procedure which al-lows for the creation of asymptotically optimal reversible networks. However, asymptotic optimality does not neces-sarily mean absolute optimality. Thus, when the algorithm terminates, and a network is created, simplication proce-dures that may reduce the number of gates in the network can be applied.