An Efficient Synthesis of Reversible Fault Tolerant Circuit for Sorting Algorithms Optimization

This thesis submitted in partial fulfillment of the requirements for the degree of Bachelor of Science in Computer Science and Engineering of East West University, Dhaka, Bangladesh.Conventional circuits dissipates power by losing bits of information whereas reversible circuit recovers bit loss through unique input-output mapping for all possible combination and logically dissipate zero heat. In addition, fault tolerant reversible circuit consists of only reversible parity preserving gates can detect faulty signal from its primary outputs. Moreover, Quantum computers, more specifically quantum circuits requires their computational process maintain the reversibility during entire computation. On the other hand, use of sorting algorithms to manage large volume of data is increasing. In these consequences, this research studies the optimization of Selection sort, Bubble Sort, Merge Sort and Insertion Sort in reversible fault tolerant circuits composed of only reversible fault tolerant Fredkin gates. The proposed algorithm performs sorting among optimal implementations of designed essential functions to implement the reversible fault tolerant boolean function. The proposed optimization algorithm also considers both gate and quantum level circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are minimized. The proposed scheme is evaluated with respect to existing approaches which showed that the proposed method performs much and are much more scalable