New Generation Computing, 21(2003)297-317
Ohmsha, Ltd. and Springer-Verlag

Invited Paper
Transformation Rules for CNOT-based Quantum Circuits and Their Applications

Kazuo IWAMA
Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
Quantum Computation and Information Project, ERATO, JST
406, Iseya-cho, Kamigyo-ku, Kyoto 602-0873, Japan
iwama@kuis.kyoto-u.ac.jp

Shigeru YAMASHITA
NTT Communication Science Laboratories
2-4, Hikaridai, Seika-cho Soraku-gun, Kyoto 619-0237, Japan
Quantum Computation and Information Project, ERATO, JST
406, Iseya-cho, Kamigyo-ku, Kyoto 602-0873, Japan*
ger@kuis.kyoto-u.ac.jp

Received 10 October 2002
Revised manuscript received 30 April 2003

Abstract

This paper introduces a simple but nontrivial set of local transformation rules for designing Control-NOT(CNOT)-based combinatorial circuits. We also provide a proof that the rule set is complete, namely, for any two equivalent circuits, S₁ and S₂, there is a sequence of transformations, each of them in the rule set, which changes S₁ to S₂. 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.

Keywords: Quantum Circuit, CNOT Gate, Local Transformation Rules, Proof System.

(Footnote)
* Currently Graduate School of Information Science, Nara Institute of Science and Technology

[Back]