The paper discusses the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The Shannon gate complexity function $L(n, q)$ for a reversible circuit, implementing a Boolean transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$, is defined as a function of $n$ and the number of additional inputs $q$. The general lower bound $L(n,q) \geq \frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}$ for the gate complexity of a reversible circuit is proved. An upper bound $L(n,0)...

Topics: Emerging Technologies, Computing Research Repository

Source: http://arxiv.org/abs/1412.2662