|
Bulletin of Irkutsk State University. Series Mathematics, 2011, Volume 4, Issue 4, Pages 12–26
(Mi iigum129)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli
S. F. Vinokurov, A. S. Frantseva East Siberian State Academy of Education, 6, N. Naberezhnaya St., Irkutsk, 664011
Abstract:
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.
Citation:
S. F. Vinokurov, A. S. Frantseva, “An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli”, Bulletin of Irkutsk State University. Series Mathematics, 4:4 (2011), 12–26
Linking options:
https://www.mathnet.ru/eng/iigum129 https://www.mathnet.ru/eng/iigum/v4/i4/p12
|
Statistics & downloads: |
Abstract page: | 223 | Full-text PDF : | 177 | References: | 29 |
|