Geodesic
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
Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 8-26.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$.
Keywords: reversible circuits, circuit complexity, circuit depth, computations with memory. 
@article{DM_2020_32_1_a1,
     author = {D. V. Zakablukov},
     title = {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},
     journal = {Diskretnaya Matematika},
     pages = {8--26},
     publisher = {mathdoc},
     volume = {32},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_1_a1/}
}
TY  - JOUR
AU  - D. V. Zakablukov
TI  - 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
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 8
EP  - 26
VL  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_1_a1/
LA  - ru
ID  - DM_2020_32_1_a1
ER  - 
%0 Journal Article
%A D. V. Zakablukov
%T 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
%J Diskretnaya Matematika
%D 2020
%P 8-26
%V 32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_1_a1/
%G ru
%F DM_2020_32_1_a1
D. V. Zakablukov. 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. Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 8-26. http://geodesic.mathdoc.fr/item/DM_2020_32_1_a1/

[1] Shannon C. E., “The synthesis of two-terminal switching circuits”, Bell System Tech. J., 28:8 (1949), 59–98 | DOI | MR

[2] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986, 384 pp. | MR

[3] Lupanov O. B., “Ob odnom metode sinteza skhem”, Izv. vuzov. Radiofizika, 1:1 (1958), 23–26

[4] Lupanov O. B., “O skhemakh iz funktsionalnykh elementov s zaderzhkami”, Problemy kibernetiki, no. 23, Nauka, M., 1970, 43–81

[5] Karpova N. A., “O vychisleniyakh s ogranichennoi pamyatyu”, Matematicheskie voprosy kibernetiki, no. 2, Nauka, M., 1989, 131–144

[6] Feynman R., “Quantum mechanical computers”, Optic News, 11:2 (1985) | DOI | MR

[7] Maslov D. A., Reversible Logic Synthesis, Ph. D. Thesis, 2003, 165 pp. | MR

[8] Shende V. V., Prasad A. K., Markov I. L., Hayes J. P., “Synthesis of reversible logic circuits”, IEEE Trans. Computer-Aided Des. of Integr. Circuits and Systems, 22:6 (2006), 710–722 | DOI

[9] Zakablukov D. V., “O slozhnosti obratimykh skhem, sostoyaschikh iz funktsionalnykh elementov NOT, CNOT i 2-CNOT”, Diskretnaya matematika, 28:2 (2016), 12–26 ; Zakablukov D. V., “On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates”, Discrete Math. Appl., 27:1 (2017), 57–67 | DOI | DOI | MR | Zbl

[10] Zakablukov D. V., “Otsenka glubiny obratimykh skhem iz funktsionalnykh elementov NOT, CNOT i 2-CNOT”, Vestnik Mosk. un-ta, ser. «Matem. Mekh.», 2016, no. 3, 3–12 | MR | Zbl