General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates

Abstract

The paper discusses the gate complexity and the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates in the case, when the number of additional inputs is limited. We study Shannon's gate complexity function $L(n,q)$ and depth function $D(n,q)$ for a reversible circuit implementing a Boolean transformation $f:{\mathbb{Z}}_2^n\to {\mathbb{Z}}_2^n$ with $8n<q\lesssim n{2}^{n-o(n)}$ additional inputs. The general upper bounds $L(n,q)\lesssim 2^n+8n{2}^n/({\log }_2(q-4n)-{\log }_{2}n-2)$ and $D(n,q)\lesssim 2^{n+1}(2,5+{\log }_{2}n-{\log }_2({\log }_2(q-4n)-{\log }_{2}n-2))$ are proved for this case.

In Russian, 19 pages, 5 figures