Author(s)： Issei Sakashita

J. Math-for-Ind. 5B (2013) 93-101.

• File： JMI2013B-2.pdf (157KB)

Abstract
We introduce a complete transformation rule set and a minimal equation set for controlled-NOT (CNOT)-based quantum circuits. Using these rules, quantum circuits that compute the same Boolean function are reduced to a same normal form. We can thus easily check the equivalence of circuits by comparing their normal forms. By applying the Knuth-Bendix completion algorithm to a set of modified 18 equations introduced by Iwama et al. 2002 [IKY02], we obtain a complete transformation rule set (i.e., a set of transformation rules with the properties of ‘termination’ and ‘confluence’). Our transformation rule set consists of 114 rules. Moreover, we found a minimal subset of equations for the initial equation set.

Keyword(s).　 quantum circuit, string rewriting system