Transformation rules for CNOT-based quantum circuits and their applications
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-1 and S-2, there is a sequence of transformations, each of them in the rule set, which changes S-1 to S-2. 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.
quantum circuit local transformation rules cnot gate proof system