Reversible Circuit Synthesis using Evolutionary Algorithm

With the prospect of availability of quantum computers in not-so-distant future, research on the synthesis and testing of reversible logic circuits have gained momentum in recent years. There are many existing works for the synthesis of reversible logic circuits, some of them being exact while some others approximate and based on some heuristics. Many of these methods work for reasonably smaller circuits, but fail with the increase in the number of inputs, either in terms of large memory and computation time requirements, or in terms of failure in arriving at the solution. In this paper, we have proposed a synthesis approach that uses Genetic Algorithm (GA) for searching the solution space, and is based on a gate library consisting of NOT, CNOT and generalized Toffoli gates. This method gives good solutions to circuits with up to 5 or 6 inputs very fast. A divide-and-conquer approach is also proposed towards the end of the paper as a future work using which larger circuits can be handled.