Вентильная сложность обратимых схем как мера сложности четных подстановок

Рассмотрен вопрос сложности четных подстановок через оценку вентильной сложности задающих их обратимых схем, состоящих из вентилей NOT, CNOT и 2-CNOT. Доказано, что все четные подстановки на множестве Zⁿ₂ задаются обратимой схемой, не использующей дополнительные входы, с вентильной сложностью, эквивалентной с точность до порядка n2ⁿ/ log₂n; оставшиеся четные подстановки задаются обратимой схемой, не использующей дополнительные входы, с меньшей вентильной сложностью. Установлено, что любая четная подстановка на множестве Zⁿ₂ реализуется обратимой схемой с вентильной сложностью < 2ⁿ⁺¹ при использовании ~ 5 • 2ⁿ/n дополнительных входов. Для всех четных подстановок применение дополнительных входов позволяет снизить вентильную сложность реализующих их обратимых схем.

Литература

[1] Shannon C.E. The synthesis of two-terminal switching circuits // Bell System Technical Journal. 1949. Vol. 28. No. 1. С. 59-98.

[2] Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

[3] Interlando J.C. Toward a Theory of One-way Functions via Gate Complexity of Boolean Functions // Ph. D. Thesis, University of Notre Dame, Indiana, USA, 2006. 100 p.

[4] Feynman R. Quantum Mechanical Computers // Optic News. 1985. Vol. 11. No. 2. P. 11-20.

[5] Maslov D.A. Reversible Logic Synthesis // Ph. D. Thesis, University of New Brunswick Fredericton, N.B., Canada, 2003. 165 p.

[6] Закаблуков Д.В. Снижение вентильной сложности обратимых схем без использования таблиц эквивалентных замен композиций вентилей // Наука и образование: Электрон. науч.-техн. издание. 2014. № 3. DOI: 10.7463/0314.0699195 (дата обращения: 20.04.2014).

[7] Shende V.V., Prasad A.K., Markov I.L., Hayes J.P. Synthesis of Reversible Logic Circuits // IEEE Trans. on CAD. 2003. Vol. 22. No. 6. P. 710-722.

[8] Закаблуков Д.В., Жуков А.Е. Исследование схем из обратимых логических элементов // Информатика и системы управления в XXI веке: Сб. трудов молодых ученых, аспирантов и студентов. № 9. М.: МГТУ им. Н.Э. Баумана, 2012. С. 148-157.

[9] Закаблуков Д.В. Быстрый алгоритм синтеза обратимых схем на основе теории групп подстановок // Прикладная дискретная математика. 2014. № 2. С. 101-109.

[10] Khlopotine A.B., Perkowski M.A., Kerntopf P. Reversible Logic Synthesis by Iterative Compositions // International Workshop on Logic Synthesis. 2002. P. 261-266.

[11] Yang G., Song X., Hung W.N., Perkowski M.A. Fast Synthesis of Exact Minimal Reversible Circuits Using Group Theory // ASP-DAC’05 Proceedings of the 2005 Asia and South Pacific Design Automation Conference. 2005. P. 1002-1005. DOI: 10.1145/1120725.1120777 (дата обращения: 20.04.2014).

[12] Miller D.M., Maslov D.A., Dueck G.W. A Transformation Based Algorithm for Reversible Logic Synthesis // DAC’03 Proceedings of the 40th annual Design Automation Conference. 2003. P. 318-323. DOI: 10.1145/775832.775915 (дата обращения: 20.04.2014).

[13] Miller D.M. Spectral and Two-Place Decomposition Techniques in Reversible Logic // MWSCAS’02 Proceedings of the 45th Midwest Symposium on Circuits and Systems Conference. 2002. P. 493-496. DOI: 10.1109/MWSCAS.2002.1186906 (дата обращения: 20.04.2014).

[14] Saeedi M., Sedighi M., Zamani M.S. A Novel Synthesis Algorithm for Reversible Circuits // ICCAD’07 Proceedings of International Conference on Computer-Aided Design. 2007. P. 65-68. DOI:10.1109/ICCAD.2007.4397245 (дата обращения: 20.04.2014).

[15] Yang G., Song X., Hung W.N., Xie F., Perkowski M.A. Group Theory Based Synthesis of Binary Reversible Circuits // TAMC’06 Proceedings of the Third international conference on Theory and Applications of Models of Computation. 2006. P 365-374. DOI: 10.1007/11750321_35 (дата обращения: 20.04.2014).