Implementing an arbitrary reversible logic gate
Yvan Van Rentergem, Alexis De Vos, Leo Storme · Journal of Physics A Mathematical and General · 2005
The (2 w )! reversible logic gates of width w , i.e. reversible logic gates with w inputs and w outputs, together with the action of cascading, form a group R . We define a subgroup K , consisting of the SWITCHED gates. There are [(2 w −1 )!] 2 such gates. They partition the group R into 2 w −1 + 1 double cosets. This allows us to decompose an arbitrary reversible gate into the cascade of three gates: a SWITCHED gate, an upside-down simple control gate and a second SWITCHED gate. We present an algorithm to perform this factorization, and thus provide a method of implementing an arbitrary reversible gate into hardware. The algorithm can be used to automate the implementation of a reversible function in future (c-MOS) technologies, realizing low-cost computing.