On the dependence of the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates on the number of additional inputs

D. V. Zakablukov

Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 8-26

Résumé

The paper is concerned with the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates under constraints on the number of additional inputs. We study the Shannon functions for the complexity $L(n, q)$ and depth $D(n,q)$ of a reversible circuit implementing a map $f\colon \mathbb{Z}_2^n \to \mathbb{Z}_2^n$ under the condition that the number of additional inputs $q$ is in the range $8n q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, where $\phi(n) \to \infty$ and $n \mathop / \phi(n) - \log_2 n \to \infty$ as $n \to \infty$. We establish the upper estimates $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ and $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ for this range of $q$. The asymptotics $L(n,q) \asymp n2^n \mathop / \log_2 q$ is established for $q$ such that $n^2 \lesssim q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, where $\phi(n) \to \infty$ and $n \mathop / \phi(n) - \log_2 n \to \infty$ as $n \to \infty$.

Détail

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