A Study of Optimal 4-bit Reversible Toffoli Circuits and Their Synthesis

Understand

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 huge search space (16! {\approx} 2^{44} 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.