Metody konstrukcji optymalnych układów odwracalnych

• Autorzy: Szyprowski M. , Kerntopf P.

Warianty tytułu

EN

Techniques for constructing optimal reversible circuits

• Języki publikacji: PL

Abstrakty

PL

Dopiero w 2010 roku, po całej dekadzie badań, opracowano pierwszą metodę syntezy optymalnych układów odwracalnych dla dowolnych funkcji czterech zmiennych. Układy te budowane były ze standardowej biblioteki bramek odwracalnych NCT, mających wyłącznie tzw. pozytywne sterowanie. W pracy opisujemy wyniki naszych rozszerzeń tej metody na przypadek minimalizowania kosztu kwantowego dla układów o zadanej liczbie bramek, a także na układy budowane z bramek NCT o mieszanym sterowaniu (tzn. zarówno o pozytywnym, jak i negatywnym).

EN

computation (i.e. bijective mapping). This emerging research area has applications in many new areas of computer science, e.g. quantum computing, nanotechnologies, optical computing, digital signal processing, communications, bioinformatics, cryptography as well as in low power computation. Recent advances consist in reducing numbers of gates, garbage bits or quantum cost. Synthesis of optimal reversible circuits is a very hard problem even for small input/output circuits. In 2010 a method for construction of 4-input/output optimal circuits was developed for circuits constructed using reversible gates from NCT library [5]. In the paper we present a summary of the results of our extensions to this method. We have developed an approach for minimization of quantum cost of the 4-input/output circuits [7]. Our computational experiments have been conducted for two sets of reversible gates: a standard NCT library and extended mixed-polarity NCT library, which consists of gates with both positive and negative control lines. Using our tools we have found circuits for the known reversible benchmarks which have lower quantum cost than any of the best known implementations so far. Based on the data of our experiments we have made a statistical comparison of the optimal circuits built from standard NCT and libraries.

Słowa kluczowe

PL

układy odwracalne; synteza logiczna; układy kwantowe

EN

reversible circuits; logic synthesis; quantum circuits

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 7
• Strony: 647--649
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Szyprowski M.

autor

Kerntopf P.

• Politechnika Warszawska, Wydział Elektroniki, Instytut Informatyki, ul. Nowowiejska 15/19, 00-665 Warszawa,

Bibliografia

• [1] De Vos A.: Reversible Computing. Fundamentals, Quantum Computing and Applications. Wiley-VCH, Berlin 2010.
• [2] Szyprowski M., Kerntopf P.: Realizacje układów odwracalnych w technologiach półprzewodnikowych. Pomiary Automatyka Kontrola, vol. 57, nr 8, ss. 911-913, 2011.
• [3] Shor P. W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. of Computing, vol. 26, pp. 1484-1509, 1997.
• [4] Nielsen M., Chuang I.: Quantum Computation and Quantum Information. Cambridge University Press 2000.
• [5] Golubitsky O., Falconer S. M., Maslov D.: Synthesis of the optimal 4-bit reversible circuits. Design Automation Conf., pp. 653-656, 2010.
• [6] Golubitsky O., Maslov D.: A study of optimal 4-bit reversible Toffoli circuits and their synthesis. IEEE Trans. on Computers, 2012, accepted, dostępny jako arXiv:1103.2686.
• [7] Szyprowski M., Kerntopf P.: Reducing quantum cost in reversible Toffoli circuits, Proc. 10th International Reed-Muller Workshop, pp. 127-136, 2011.
• [8] Szyprowski M., Kerntopf P.: An approach to reducing quantum cost in reversible circuits, Proc. 11th IEEE International Conference on Nanotechnology, pp. 1521-1526, 2011.
• [9] Maslov D.: Reversible Logic Synthesis Benchmarks Page, http://www.cs.uvic.ca/~dmaslov.
• [10] Wille R., Grosse D., Teuber L., Dueck G. W. and Drechsler R., RevLib: An online resourse for reversible functions and reversible circuits, http://www.revlib.org.
• [11] Markov I. L., Saeedi M.: Constant-optimized quantum circuits for modular multiplication and exponentiation, arXiv:1202.6614, 2012.
• [12] Maslov D., Saeedi M.: Reversible circuit optimization via leaving the Boolean domain, IEEE Trans. on CAD, vol. 30, pp. 806-816, 2011.