Nowe reguły przesuwania bramek w układach odwracalnych

• Autorzy: Szyprowski M. , Kerntopf P.

Warianty tytułu

EN

New rules for moving gates in reversible circuits

• Języki publikacji: PL

Abstrakty

PL

Jedną z możliwości redukcji układów odwracalnych daje przesuwanie bramek. W pracy zaproponowano nowe reguły takich przesunięć dla układów budowanych ze standardowej biblioteki bramek odwracalnych NCT. Umożliwiają one eliminację bramek o dużej liczbie wejść/wyjść, które mają największy tzw. koszt kwantowy. Opracowane przez nas reguły mogą być stosowane dla dowolnej liczby wejść układu. Umożliwia to projektowanie układów odwracalnych o zredukowanym koszcie kwantowym. Podane przez nas przykłady pokazują, że oszczędności w porównaniu z układami publikowanymi w literaturze mogą być znaczne.

EN

Synthesis of reversible logic circuits is the most intensively studied topic of the research area called reversible computation (circuits are reversible if they represent bijective mappings). This new research area has applications in many fields 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. Some reversible circuit synthesis algorithms generate circuits in which majority of gates have large or even maximal size (i.e. equal to the number of inputs/outputs. However, quantum cost of multi-control generalized Toffoli gates is very high. In this paper it is shown how to reduce the quantum cost of circuits by eliminating most of large gates or even all of them. Namely, a new subset of moving rules useful for reducing the quantum cost is presented. Using this subset, it is possible to reduce the number of maximal-size gates to zero for even functions, and to one for odd functions, according to the known theorem. In the paper substantial savings in the quantum cost are presented for designs taken from recent publications.

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: 2013
• Tom: R. 59, nr 8
• Strony: 787--789
• Opis fizyczny: Bibliogr. 8 poz., rys., tab., wzory

Twórcy

autor

Szyprowski M.

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

autor

Kerntopf P.

• Politechnika Warszawska, Wydział Elektroniki, Instytut Informatyki, ul. Nowowiejska 15/19, 00-665 Warszawa
• Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej, ul. Pomorska 149/153, 90-236 Łódź

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] Iwama K., Kambayashi Y., Ymashita S.: Transformation Rules for Designing CNOT-based Quantum Circuits. Proc. Design Automation Conf., pp. 419-424, 2002.
• [4] Shende V. V., Prasad A. K., Markov I. L., Hayes J. P.: Synthesis of Reversible Logic Circuits. IEEE Trans. on CAD, vol. 22, pp. 710-722, 2003.
• [5] Miller D. M., Maslov D., Dueck G. W.: A Transformation Based Algorithm for Reversible Logic Synthesis. Proc. Design Automation Conf., pp. 318-323, 2003.
• [6] Rahman M. M., Dueck G. W.: Properties of Quantum Templates. R. Glück, T. Yokoyama (eds.) Reversible Computation, vol. 7581, pp. 125-137, Springer-Verlag, Berlin Heidelberg, 2013.
• [7] Nayeem N. M., Rice J. E.: A Shared-Cube Approach to ESOP-Based Synthesis of Reversible Logic. Facta Universitatis, Series: Electronics and Energetics, vol. 24, pp. 385-402, 2011.
• [8] Sanaee Y., Dueck G. W.: Generating Toffoli Networks from ESOP Expresions. Proc. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 715-719, 2009.