Transformation rules for CNOT-based quantum circuits and their applications

This paper introduces a simple but nontrivial set of local transformation rules for designingControl-NOT(CNOT)-based combinatorial circuits. We also provide a proof that the rule set iscomplete, namely, for any two equivalent circuits,S ₁ andS ₂, there is a sequence of transformations, each of them in the rule set, which changesS ₁ toS ₂. Two applications of the rule set are also presented. One is to simulate Resolution with only polynomial overhead by the rule set. Therefore we can conclude that the rule set is reasonably powerful. The other is to reduce the cost of CNOT-based circuits by using the transformations in the rule set. This implies that the rule set might be used for the practical circuit design. Currently Graduate School of Information Science, Nara Institute of Science and Technology Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Shigeru Yamashita, Ph.D.: Associate Professor of Graduate School of Information Science, Nara Instutute of Science and Technology, Nara 630-0192, Japan. He received his B.E., M.E. and Ph.D. degrees in information science from Kyoto University, Kyoto, Japan, in 1993, 1995 and 2001, respectively. His research interests include new type of computer architectures and quantum computation. He received the 2000 IEEE Circuits and Systems Society Transactions on Computer-Aided Design of Integrated Circuits and Systems Best Paper Award.