Zakablukov

This paper studies the problem of reducing the gate complexity of the reversible circuits consisting of NOT and k-CNOT gates without using replacement tables. Generalization of k-CNOT gate is made for the case of zero value at some of the gate control inputs. For such generalized k-CNOT gates the equivalent replacements for the reversible gates compositions are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Application of the equivalent replacements for reduction of the gate complexity of the abstract reversible circuit is shown.