Synthesis of the optimal 4-bit reversible circuits
Oleg Golubitsky, Sean M. Falconer, Dmitri A Maslov · 2010
Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a complexity explosion (16! ≈ 244 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage.