A Reversible Logical Circuit Synthesis Algorithm Based On Decomposition Of Cycle Representations Of Permutations

Research on reversible computing has important applications to several areas,such as signal processing,cryptography,computer graphics,nano and photonic circuits.For instance,the theory of reversible computing is one of the foundations of quantum computation.An important feature of the circuit model of quantum computing is reversibility,which is a consequence of the evolution postulate of quantum mechanics.An important problem in reversible computing is the synthesis of reversible circuits.However,there are still a series of problems in the algorithm for synthesis of reversible logic circuits for the moment,such as the scale of reversible logic circuits is too small,the cost is exorbitant,and the time and space complexity is high in the process of optimization and so on.It cannot meet the requirements of the quantum logic circuit for future quantum computing and quantum information and other fields.Therefore,it is necessary to study the synthesis and optimization techniques of reversible circuits systematically and deeply and find more efficient synthesis and optimization algorithms.Therefore,we have a deep research on the synthesis of reversible circuits,the main research work and results are as follows:1.A reversible logical circuit synthesis algorithm based on decomposition of cycle representations of permutationsA reversible function is isomorphic to a permutation and an arbitrary permutation can be represented by a series of cycles.In this work,we present a new algorithm for synthesis of reversible circuits based on the idea of exploring properties of the cycle representation of permutations.It consists of two parts,the first part used the Number of reversible function's Different Bits(NDBs)to decide whether the NOT gate should be added to decrease the Hamming distance of the input and output vectors.The second part was based on the properties of permutations and its cycle representations,decomposed the cycles to make the permutation closer to the identity permutation and finally turn into the identity permutation,it was realized by using totally controlled Toffoli gates with positive and negative controls.Our algorithm provides a new idea and it can still be improved to optimize the final result.Our approach can be extended for circuit synthesis of 4 bits and even more bits.2.Research on speed-up techniques for reversible circuit synthesis algorithm based on CUDACUDA is the most widely used common parallel computing architecture.With the aid of the parallel processing capability of GPU(Graphics Processing Unit),the running speed and the corresponding solving ability of the program can be greatly improved without additional cost.In this part,we will implement a fast algorithm for calculating the Hash function and calculate the permutable products to simulate the cascade of reversible circuits with the aid of CUDA parallel architecture,and the acceleration ratio is studied respectively.A parallel implementation of an efficient reversible circuit synthesis algorithm is running on the CUDA computing platform.