Reversible Circuit Optimization based on Tabu Search

Abstract

An algorithm, based on the meta-heuristic technique known as Tabu Search, was developed to optimize reversible circuits. A set of rules that can modify the reversible circuit to be optimized are applied. The movement of gates may increase, decrease, or leave the number of gates unchanged. In this context, an algorithm was developed to control the application of these rules. The idea of the proposed algorithm is to divide the reversible circuit into neighborhoods and perform a Tabu search to find the best local solution in each neighborhood, penalizing the rules that were already applied in the iteration. The results of optimized benchmark functions shows the efficiency of the algorithm, reducing reversible circuits by up to 62%.