An Evolutionary Approach to Reversible Logic Synthesis using Output Permutation

The area of reversible circuit synthesis has become very important in recent years with the growing emphasis on low-power design and quantum computation. Many synthesis approaches have been reported over the last two decades. For small functions exact solutions can be computed. Otherwise, heuristics have to be applied that are either based on transformations or a direct mapping from a given data structure. Recently, it was shown that significant reduction in the cost of the synthesized circuits can be obtained, if the ordering of the output lines is changed. The drawback of the approach was that it can only be applied to smaller sized circuits. In this paper, an evolutionary approach for obtaining a good ordering of the output variables is proposed, which can be used for larger sized circuits as well. The method does not require explicit synthesis of the reversible circuit netlist. Experimental results are shown with respect to a transformation based synthesis tool. Reductions of up to 98% can be observed with an average reduction of 64.4% for larger circuits.