Study On Multi-objective Evolutionary Algorithm For Automatic Synthesis Of Quantum Reversible Logic

With the development of scientific technology and computer industry, the System-on-a-chip (SOC) is becoming a main feature of integrated circuits (IC). The integration of computer chips is increasing constantly by following Moore's Law, the faster, smaller, and more complex system-level chips have emerged. Though improvement of the integration can significantly enhance the performance of computers, it leads to two problems:1) with the increase of clock frequency and the growing number of transistors packed onto a chip, the energy consumption of computer will continue to increase, which means that heat dissipation will be a big problem; 2) with the development of manufacture process, the size of crystal diodes will reach the level of atoms, and the quantum effect of electron will emerge, which will lead to the failure of classical physical law.The reversible logic circuits (RLC) are a sort of novel circuits which implement logic operations in a reversible manner. It can avoid information loss and energy dissipation resulting from irreversible logic bit operations. On the other hand, quantum computers adopt the mechanism of quantum mechanics and obey the quantum physical law, which can solve the failure of classical physical law. In addition, quantum computers can be equivalent to a quantum Turing machine which can be equivalent to quantum logic circuits. A quantum logic circuit is a combination and cascade of quantum logic gates. Because quantum logic gates are of reversibility which is the basic characteristic of quantum computing, the reversible computing is a core issue of quantum computing, quantum logic circuits are the best realization form of RLC, and the synthesis of reversible logic is a key technology to achieve quantum computers. In a word, the reversibility will be a basic characteristic of circuits design in future, and quantum RLC are not only the unique way to reduce the further IC's power dissipation but also a precondition to implement the quantum computer. Thus, the study of synthesis of quantum reversible logic will contribute to the progresses of ultra-low power IC's design and quantum computing.As there is a big difference between quantum RLC and common irreversible circuits, the synthesis approach of quantum RLC is very different from the existing irreversible logic circuits, and synthesis and optimization of quantum RLC are more difficult. At present, the conventional synthesis approaches of quantum reversible logic were generally not enough mature, the automation is still within a lower degree and lack of practicality. The main reason is that the synthesis of quantum reversible logic is after all a sort of multi-objective optimization problems with the strong constraints and the lack of domain knowledge. The synthesis of quantum reversible logic has already become a worldwide research hotspot, but it is also confronted with a lot of challenging problems. The evolutionary design uses the high-performance auto-solving capabilities of evolutionary computation to find the design features with the expected results by artificial evolution, which does not depend on the priori knowledge and human participation, so it can be used to explore a broader design space and address the complex problems which can not be solved by conventional approaches as a result of the lack of the related knowledge and experience, and then achieve the automatic design of related systems. Thus, the evolutionary design is an effective way to solve the complexity of synthesis of quantum reversible logic.In this dissertation, the basic principles, technical characteristics and recent developments on the synthesis of quantum reversible logic are systematically discussed. By applying evolutionary design techniques to the synthesis of quantum reversible logic, the automatic synthesis approaches are studied which can automatically generate, simplify and optimize the quantum RLC with the less computing and human participation in order to improve the level of synthesis and the degree of practicality. Then, with the focus on improving the evolutionary algorithm, encoding and decoding scheme, multi-objective fitness evaluation methods, and automatic simplification and repair strategies, two automatic synthesis approaches for quantum reversible logic are investigated theoretically and experimentally. Some positive results have been obtained:(1) After introducing the evolutionary algorithms, especially on its categories and the structure and characteristics of each branch, the biological mechanism and general methods on improving the evolutionary speed and convergence possibility are discussed in detail by using sexual reproduction, Baldwin effect, and self-adaptation mechanism in order to overcome the defects of genetic algorithms such as lower search speed, premature convergence, stochastic roaming, and lower accuracy of ultimate solutions. According to the characteristics of automatic synthesis of quantum reversible logic, a hybrid self-adaptive genetic algorithm based on sexual reproduction and Baldwin effect (BSAGA) is proposed. Then, the global convergence analysis of BSAGA is presented in detail.(2) On the basis of analysis and comparison among some available multi-objective evolutionary algorithms, an adaptive multi-objective discrete differential evolution (MDDE) is proposed and discussed by the requirement of automatic synthesis of quantum reversible logic. By introducing differential evolution to multi-objective optimization, MDDE adopts a new adaptive discrete differential evolution strategy to enhance the ability of global exploration so as to achieve better Pareto approximate solutions. Moreover, for keeping good diversity, MDDE integrates fast Pareto sorting strategy and truncating operation based on crowding density and rank.(3) According to the related literatures and simulation results, the common quantum logic gates are analyzed and compared, and the most applicable gates are selected to build a universal and complete quantum logic gate-level component library-NCT device library for automatic synthesis of quantum reversible logic. Based on the above component library, an efficient encoding and decoding scheme is studied (i.e., the net-list-level coding scheme-based on gate-level array model of quantum reversible logic) which supports automatic generation of the structure of quantum RLC, some practical synthesis sub-objectives, two efficient fitness evaluation methods (including dynamic multi-objective evaluation method and multi-objective evaluation method based on Pareto-optimal), and the automatic simplification and repair strategies (i.e., a'pre-bit priority'repair mechanism and a knowledge-based local transformation strategy), etc.(4) For the automatic synthesis of quantum reversible logic, BSAGA and MDDE are adopted as a basis of evolutionary design, and give attention to the multiple synthesis sub-objectives such as the expected function, realization cost and higher utilization ratio of circuit resource at the same time. Moreover, by combining the above encoding and decoding scheme, multi-objective evaluation methods, and automatic simplification and repair strategies, an automatic synthesis approach for quantum reversible logic based on dynamic multi-objective evaluation and an automatic synthesis approach for quantum reversible logic based on Pareto-optimal are proposed respectively in this dissertation. Finally, two proposed approaches are analyzed and compared, and the synthesis experiments verify that they are valid and advanced.In this dissertation, some effective exploration and attempt are made to put forward the innovative solutions of several key issues on the synthesis of quantum reversible logic. Theoretical analysis and experimental results show that the proposed automatic synthesis approaches can solve the corresponding problems effectively and efficiently, and they achieve great complementarily and improvement to the existing conventional approaches. Thus, the researches of this dissertation have some practical application value and theoretical value for improving the level of synthesis and the degree of practicality of synthesis of quantum reversible logic, and make some contributions to promote the development of ultra-low-power IC's design and quantum computing.