On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates

D. V. Zakablukov

Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 12-26

Résumé

The paper is concerned with the problem of complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. For a reversible circuit implementing a map $f\colon \ZZ_2^n \to \ZZ_2^n$ we define the Shannon complexity function $L(n, q)$ as a function of $n$ and the number $q$ of additional inputs in the circuit. We prove the lower estimate $L(n,q) \geqslant \frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}$ for the complexity of a reversible circuit and derive the upper estimate $L(n,0) \leqslant 48n2^n(1+o(1)) \mathop / \log_2n$ if there are no additional inputs. The asymptotic upper estimate for the complexity is shown to be $L(n,q_0) \lesssim 2^n$ with $q_0 \sim n2^{n-o(n)}$ additional inputs.

Détail

Keywords: reversible circuit, circuit complexity, computations with memory.