Synthesis of reversible circuits for large reversible functions

This paper presents a new algorithm MP (multiple pass) to synthesize large reversible binary circuits without ancilla bits. The well- known MMD algorithm for synthesis of reversible circuits requires to store a truth t able (or a Reed-Muller - RM transform) as a 2n vector to represent a reversible function of n variables. Th is rep- resentation prohibits synthesis of large functions. However, in MP we do not store such an exponentially growing data structure. The values of minterms are calculated in MP dynamically, one-by-one, from a set of logic equations that specify the re- versible circuit to be designed. This allows for synthesis o f large scale reversible circuits (30-bits), which is not possible with any existing algorithm. In addition, our unique multi-pass approach where the circuit is synthesized with various, yet specific, minterm orders yields quasi-optimal solution. The algorithm returns a description of the quasi-optimal circuit with respect to gate count or to it s "quantum cost". Although the synthesis process in MP is relatively slower, the soluti on is found in real-time for smaller circuits of 8 bits or less.