Asymptotic bounds of depth for a reversible circuit consisting of NOT, CNOT and 2-CNOT gates

Abstract

The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. Reversible circuit depth function $D(n,q)$ for a circuit implementing a transformation $f:{\mathbb{Z}}_2^n\to {\mathbb{Z}}_2^n$ is introduced as a function of $n$ and the number of additional inputs $q$. It is proved that for the case of implementing a permutation from $A({\mathbb{Z}}_2^n)$ with a reversible circuit having no additional inputs the depth is bounded as $D(n,0)\gtrsim 2^n/(3{\log }_{2}n)$. It is proved that for the case of implementing a transformation $f:{\mathbb{Z}}_2^n\to {\mathbb{Z}}_2^n$ with a reversible circuit having $q_0\sim 2^n$ additional inputs the depth is bounded as $D(n,q_0)\lesssim 3n$.

arXiv commentIn Russian, 14 pages, 4 figures