Estimation of the Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates / D. V. Zakablukov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2016. № 3. P. 3-12 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 89-97].

The paper discusses the asymptotic depth of a reversible circuits 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 q of additional inputs. It is proved that for the case of implementation of 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 also proved that for the case of 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.

№ 3/2016