On Asymptotic Gate Complexity and Depth of Reversible Circuits Without\n Additional Memory

Reversible computation is one of the most promising emerging technologies of\nthe future. The usage of reversible circuits in computing devices can lead to a\nsignificantly lower power consumption. In this paper we study reversible logic\ncircuits consisting of NOT, CNOT and 2-CNOT gates. We introduce a set $F(n,q)$\nof all transformations $\\mathbb Z_2^n \\to \\mathbb Z_2^n$ that can be\nimplemented by reversible circuits with $(n+q)$ inputs. We define the Shannon\ngate complexity function $L(n,q)$ and the depth function $D(n,q)$ as functions\nof $n$ and the number of additional inputs $q$. First, we prove general lower\nbounds for functions $L(n,q)$ and $D(n,q)$. Second, we introduce a new group\ntheory based synthesis algorithm, which can produce a circuit $\\mathfrak S$\nwithout additional inputs and with the gate complexity $L(\\mathfrak S) \\leq 3n\n2^{n+4}(1+o(1)) \\mathop / \\log_2 n$. Using these bounds, we state that almost\nevery reversible circuit with no additional inputs, consisting of NOT, CNOT and\n2-CNOT gates, implements a transformation from $F(n,0)$ with the gate\ncomplexity $L(n,0) \\asymp n 2^n \\mathop / \\log_2 n$ and with the depth $D(n,0)\n\\geq 2^n(1-o(1)) \\mathop / (3\\log_2 n)$.\n