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.
reversible logic, circuit depth, computations with memory.