List of issues > Series «Mathematics». 2011. Vol. 4
An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli
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.
1. Гашков С. Б. Системы счисления и их применение / С. Б. Гашков. – М. : МЦНМО, 2004. – 52 с.: ил. – (Б-ка «Математическое просвещение») вып. 29).
2. Квантовый компьютер и квантовые вычисления. Т. 2. – Ижевск : Ред. журн. «Регулярная и хаотическая динамика», 1999. – 287 c.
3. Мальцев А. И. Основы линейной алгебры / А. И. Мальцев. – М. : Наука, 1970. – 400 с.
4. Monz T. [et al.] Realization of the quantum Toffoli gate with trapped ions. arXiv:0804.0082v1 [quant-ph] 1 Apr 2008.
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. – 1981. – Vol. 14. – P. 13-23.
7. Vivek V. Shende at al. Synthesis of Reversible Logic Circuits //IEEE Transactions on Computer-Aided design of integrated circuits and systems.– 2003. – Vol. 22, N6.