Dmitri Maslov,

University Waterloo

Synthesis of the Optimal 4-bit Reversible Circuits

ABSTRACT:

Reversible circuits are an important class of computations. Currently, these circuits are most often used with regards to quantum computation. Efficient reversible circuits are critical to the efficiency of certain quantum algorithms. 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! ~ 2⁴⁴ 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 talk, I will present an algorithm, and its C++ implementation, that synthesizes an optimal circuit for any 4-bit reversible specification. My co-authors and I employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of 10,000,000 random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits requiring no more than 9 gates. 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.

COLLABORATORS:

Oleg Golubitsky, Google, Waterloo, ON, Canada Sean M. Falconer, University of Victoria, Victoria, BC, Canada