Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates

D. V. Zakablukov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2016), pp. 3-12

Résumé

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$.