The decomposition of an arbitrary reversible logic circuit
Alexis De Vos, Yvan Van Rentergem, Koen De Keyser · Journal of Physics A Mathematical and General · 2006
The (2 w )! reversible logic circuits of width w , i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group G , isomorphic to the symmetric group . We define two conjugate subgroups G 1 and G 2 . Together they partition the group G into 2 w −1 + 1 double cosets. These allow us to decompose an arbitrary member of G into a cascade of three simpler members. This decomposition is a far relative of the well-known LU decomposition of a square matrix.