Geodesic
An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli
The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 4, pp. 12-26 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate questions of computing of the complexity of the arbitrarily given reversible function. Previously introduced the concept of reversible computation required, in particular, the concept of a reversible function. We consider various representations of reversible functions (the table of values, permutation matrices, permutations and logic circuits). As the basis of reversible circuits is considered a well-known Toffoli gates [1]. Presented sequential and parallel algorithms for computing of the complexity of the reversible function. The algorithms were run on a cluster containing 16 nodes, each of which has a Intel Pentium Dual CPU, 1,86 Gz, 1,87 Gz, 2Gb, Ethernet network 100Mbit/sek. The cluster is organized in ESSAE. We present estimates of the complexity.
Keywords: reversible functions, complexity, Toffoli gates, sequential and parallel algorithms. 
@article{IIGUM_2011_4_4_a1,
     author = {S. F. Vinokurov and A. S. Frantseva},
     title = {An approximate algorithm for computing the complexity of reversible functions in the basis of {Toffoli}},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {12--26},
     year = {2011},
     volume = {4},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a1/}
}
TY  - JOUR
AU  - S. F. Vinokurov
AU  - A. S. Frantseva
TI  - An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2011
SP  - 12
EP  - 26
VL  - 4
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a1/
LA  - ru
ID  - IIGUM_2011_4_4_a1
ER  - 
%0 Journal Article
%A S. F. Vinokurov
%A A. S. Frantseva
%T An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2011
%P 12-26
%V 4
%N 4
%U http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a1/
%G ru
%F IIGUM_2011_4_4_a1
S. F. Vinokurov; A. S. Frantseva. An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli. The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 4, pp. 12-26. http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a1/

[1] S. B. Gashkov, Sistemy schisleniya i ikh primenenie, B-ka «Matematicheskoe prosveschenie», 29, MTsNMO, M., 2004, 52 pp.

[2] Kvantovyi kompyuter i kvantovye vychisleniya, v. 2, Red. zhurn. «Regulyarnaya i khaoticheskaya dinamika», Izhevsk, 1999, 287 pp. | Zbl

[3] A. I. Maltsev, Osnovy lineinoi algebry, Nauka, M., 1970, 400 pp.

[4] Monz T. et al., Realization of the quantum Toffoli gate with trapped ions, 1 Apr 2008, arXiv: 0804.0082v1 [quant-ph]

[5] Toffoli T., Reversible Computing, Tech. Memo MIT/LCS/TM-151, MIT Lab. for Comp. Sci., 1980

[6] Toffoli T., “Bicontinuous Extensions of Invetible Combinatorial Functions”, Mathematical Systems Theory, 14 (1981), 13–23 | DOI | MR | Zbl

[7] Vivek V. Shende at al., “Synthesis of Reversible Logic Circuits”, IEEE Transactions on Computer-Aided design of integrated circuits and systems, 22:6 (2003)