Abstract:
The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function $D(n,q)$ is introduced for a circuit implementing a mapping $f\colon\mathbb{Z}_2^n\to\mathbb{Z}_2^n$ 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\colon\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$.
Key words:reversible logic, circuit depth, computations with memory.
Fulltext:
PDF file (473 kB)