On Gate Complexity of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates

Abstract

The paper discusses the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The Shannon gate complexity function $L(n,q)$ for a reversible circuit, implementing a Boolean transformation $f:{\mathbb{Z}}_2^n\to {\mathbb{Z}}_2^n$, is defined as a function of $n$ and the number of additional inputs $q$. The general lower bound $L(n,q)\ge \frac{2^n(n-2)}{3{\log }_2(n+q)}-\frac{n}{3}$ for the gate complexity of a reversible circuit is proved. An upper bound $L(n,0)⩽3n{2}^{n+4}(1+o(1))/{\log }_{2}n$ for the gate complexity of a reversible circuit without additional inputs is proved. An upper bound $L(n,q_0)\lesssim 2^n$ for the gate complexity of a reversible circuit with $q_0\sim n{2}^{n-o(n)}$ additional inputs is proved.

arXiv commentIn Russian, 18 pages, 1 figure