Geodesic
Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2016), pp. 3-12 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function $D(n,q)$ is introduced for a circuit implementing a mapping $f\colon\mathbb{Z}_2^n\to\mathbb{Z}_2^n$ as a function of $n$ and the number of additional inputs $q$. It is proved that for the case of implementing a permutation from $A(\mathbb{Z}_2^n)$ with a reversible circuit having no additional inputs the depth is bounded as $D(n, 0)\gtrsim 2^n/(3\log_2 n)$. It is proved that for the case of implementing a transformation $f\colon\mathbb{Z}_2^n\to\mathbb{Z}_2^n$ with a reversible circuit having $q_0\sim 2^n$ additional inputs the depth is bounded as $D(n,q_0)\lesssim 3n$. 
@article{VMUMM_2016_3_a0,
     author = {D. V. Zakablukov},
     title = {Estimation of the depth of reversible circuits consisting of {NOT,} {CNOT} and {2-CNOT} gates},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {3--12},
     year = {2016},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a0/}
}
TY  - JOUR
AU  - D. V. Zakablukov
TI  - Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2016
SP  - 3
EP  - 12
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a0/
LA  - ru
ID  - VMUMM_2016_3_a0
ER  - 
%0 Journal Article
%A D. V. Zakablukov
%T Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2016
%P 3-12
%N 3
%U http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a0/
%G ru
%F VMUMM_2016_3_a0
D. V. Zakablukov. Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2016), pp. 3-12. http://geodesic.mathdoc.fr/item/VMUMM_2016_3_a0/

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

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

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

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

[5] Khrapchenko V.M., “Novye sootnosheniya mezhdu glubinoi i zaderzhkoi”, Diskret. matem., 7:4 (1995), 77–85. | Zbl

[6] Zakablukov D.V., “Bystryi algoritm sinteza obratimykh skhem na osnove teorii grupp podstanovok”, Prikl. diskret. matem., 2014, no. 2, 101–109

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

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

[9] Vinokurov S.F., Frantseva A.S., “Priblizhennyi algoritm vychisleniya slozhnosti obratimoi funktsii v bazise Toffoli”, Izv. Irkut. gos. un-ta. Ser. matem., 4:4 (2011), 12–26 | Zbl

[10] Maslov D.A., Dueck G.W., Miller D.M., “Techniques for the synthesis of reversible Toffoli networks”, ACM Trans. Design Automat. Electron. Syst., 12:4 (2007) | DOI | Zbl

[11] Zakablukov D.V., “Ventilnaya slozhnost obratimykh skhem kak mera slozhnosti chetnykh podstanovok”, Vestn. MGTU im.\;N. E. Baumana. Ser. priborostr., 2015, no. 1, 67–82

[12] Abdessaied N., Wille R., Soeken M., Drechsler R., “Reducing the depth of quantum circuits using additional circuit lines”, Proc. 5th Int. Conf. Reversible Computation (Victoria, BC, Canada, 2013), 221–233 | DOI | MR | Zbl

[13] Toffoli T., “Reversible Computing”, Automata, Languages and Programming, Lect. Notes Comput. Sci., 85, Springer, Berlin–Heidelberg, 1980, 632–644 | DOI | MR

[14] Maslov D.A., Reversible Logic Synthesis, Ph. D. Thesis, 2003 http://web.cecs.pdx.edu/m̃perkows/PerkowskiGoogle/thesis_maslov.pdf