Geodesic
On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 12-26.

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

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.
Keywords: reversible circuit, circuit complexity, computations with memory. 
@article{DM_2016_28_2_a1,
     author = {D. V. Zakablukov},
     title = {On the gate complexity of reversible circuits consisting of {NOT,} {CNOT} and {2-CNOT} gates},
     journal = {Diskretnaya Matematika},
     pages = {12--26},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a1/}
}
TY  - JOUR
AU  - D. V. Zakablukov
TI  - On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 12
EP  - 26
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a1/
LA  - ru
ID  - DM_2016_28_2_a1
ER  - 
%0 Journal Article
%A D. V. Zakablukov
%T On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
%J Diskretnaya Matematika
%D 2016
%P 12-26
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a1/
%G ru
%F DM_2016_28_2_a1
D. V. Zakablukov. On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 12-26. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a1/

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

[2] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vyssh. shk., M., 2003, 384 pp. | MR

[3] N. A. Karpova, “O vychisleniyakh s ogranichennoi pamyatyu”, Matematicheskie voprosy kibernetiki, 2, Nauka, M., 1989, 131-144 | MR

[4] R. Feynman, “Quantum Mechanical Computers”, Optic News, 11:2 (1985), 11–20 | DOI | MR

[5] D. A. Maslov, Reversible Logic Synthesis, Ph. D. Thesis, 2003, 165 pp.

[6] D. V. Zakablukov, “Snizhenie ventilnoi slozhnosti obratimykh skhem bez ispolzovaniya tablits ekvivalentnykh zamen kompozitsii ventilei”, Nauka i obrazovanie. MGTU im. N. E. Baumana. Elektron. zhurn., 2014, no. 3, Mart | DOI

[7] V. V. Shende, A. K. Prasad, I. L. Markov, J. P. Hayes, “Synthesis of Reversible Logic Circuits”, IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst., 22, no. 6, 2006, 710–722 | DOI

[8] D. V. Zakablukov, A. E. Zhukov, “Issledovanie skhem iz obratimykh logicheskikh elementov”, Informatika i sistemy upravleniya v XXI veke, Sbornik trudov #9 molodykh uchenykh, aspirantov i studentov, MGTU im. N. E. Baumana, Moskva, 2012, 148–157

[9] D. V. Zakablukov, “Bystryi algoritm sinteza obratimykh skhem na osnove teorii grupp podstanovok”, Prikladnaya diskretnaya matematika, 2014, no. 2, Iyun, 101–109

[10] M. M. Glukhov, A. Yu. Zubov, “O dlinakh simmetricheskikh i znakoperemennykh grupp podstanovok v razlichnykh sistemakh obrazuyuschikh (obzor)”, Matematicheskie voprosy kibernetiki, vyp. 8, Nauka, M., 1999, 5–32 | MR