On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory

Abstract

The reversible logic can be used in various research areas, e.g. quantum computation, cryptography and signal processing. In the paper we study reversible logic circuits with additional inputs, which consist of NOT, CNOT and C\textsuperscript{2}NOT gates. We consider a set $F(n,q)$ of all transformations ${\mathbb{B}}^n\to {\mathbb{B}}^n$ that can be realized by reversible circuits with $(n+q)$ inputs. An analogue of Lupanov's method for the synthesis of reversible logic circuits with additional inputs is described. We prove upper asymptotic bounds for the Shannon gate complexity function $L(n,q)$ and the depth function $D(n,q)$ in case of $q>0$: $L(n,q_0)\lesssim 2^n$ if $q_0\sim n{2}^{n-o(n)}$ and $D(n,q_1)\lesssim 3n$ if $q_1\sim 2^n$.

arXiv commentIn English, 27 pages, 12 figures. Submission to the Computational Complexity journal. arXiv admin note: text overlap with arXiv:1504.06876