Chinese Journal of Computers   Full Text
Title	A Fast Algorithm for Synthesis of Quantum Reversible Logic Circuits
Authors	LI Zhi-Qiang1),2) CHEN Han-Wu1) XU Bao-Wen1) LI Wen-Qian1) WANG Jia-Jia1) LIU Wen-Jie1),3)
Address	1)(School of Computer Science and Engineering, Southeast University, Nanjing 210096) 2)(College of Information Engineering, Yangzhou University, Yangzhou, Jiangsu 225009) 3)(Department of Computer Science & Technology, Nanjing University of Information Science & Technology, Nanjing 210044)
Year	2009
Issue	No.7(1291—1303)
Abstract &   Background	Abstract Reversible logic finds many applications, especially in the area of quantum computing. Quantum reversible logic circuits are basic elements in quantum computer construction. Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost. The authors absorb different ideas of reversible logic circuits synthesis and present a novel and efficient algorithm which can automatically derive the positive polarity Reed-Muller expansion (RM). A solution space tree is constructed to create quantum reversible logic circuits. Firstly, floor traversal is applied globally, and depth-first search is used locally. Secondly, according to the technique of template optimization, the bound function is constructed, which can rapidly prune the branches with no or nonoptimal result. Thirdly, factors of RM are first considered, therefore the algorithm can effectively construct optimal result and saves computational cost significantly. Judging by the internationally recognized reversible functions of three variables, the proposed algorithm not only synthesizes all optimal reversible functions, but also runs extremely faster than others of the same kind. Keywords quantum circuit optimization; Reed Muller; reversible logic circuit; Toffoli gate; quantum computing Background This work is supported by the National Natural Science Foundation of China under grant Nos.60572071, 60873101, 90412014, Natural Science Foundation of Jiangsu Province under grant Nos.BK2008209, BK2007104, and Natural Science Foundation for colleges of Jiangsu Province under grant No.06KJB520137. A quantum computer is equivalent to a quantum Turing machine, which is an abstract mathematical model; and the quantum Turing machine is equivalent to a quantum logic circuit, as has been theoretically proven. Therefore, the quantum computer can be constructed by cascading and combining the quantum logical gates. How to automatically construct the desired quantum circuit with relatively small cost using appointed quantum gates? The principles of quantum logical gate cascading, the automatic production of basic quantum circuit and the optimization of quantum circuit are the foundations of the study. An effective method is used to synthesize quantum reversible logic circuits using the positive polarity Reed-Muller (RM) expansion of a reversible function. To which Agrawal and Pallav Gupta et al. have made their own contributions. They tried to improve its performance by adopting a few heuristics algorithms; however, these heuristics algorithms cannot guarantee that a solution will be found when it does exist and can hardly get optimal result. In this paper, a novel and efficient algorithm is presented, which can automatically derive RM expansion, and a solution space tree is constructed to effectively create the desired quantum reversible logic circuits. In the experiments on 3-qubit synthesis, the algorithm not only synthesizes all optimal reversible circuits, but also runs extremely faster than others of the same kind.