  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!~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. In this paper, we
present an algorithm that synthesizes an optimal circuit for any 4-bit
reversible specification. We employ several techniques to make the problem
tractable. We report results from several experiments, including synthesis of
random 4-bit permutations, optimal synthesis of all 4-bit linear reversible
circuits, synthesis of existing benchmark functions, and distribution of
optimal circuits. Our results have important implications for the design and
optimization of quantum circuits, testing circuit synthesis heuristics, and
performing experiments in the area of quantum information processing.
