On Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates

Abstract

The paper discusses the gate complexity of reversible circuits with the small number of additional inputs consisting of NOT, CNOT and 2-CNOT gates. We study Shannon's gate complexity function $L(n,q)$ for a reversible circuit implementing a Boolean transformation $f:{\mathbb{Z}}_2^n\to {\mathbb{Z}}_2^n$ with $q⩽O(n^2)$ additional inputs. The general bound $L(n,q)\asymp n{2}^n/{\log }_{2}n$ is proved for this case.

In Russian, 9 pages