Projektowanie odwracalnych układów w architekturze LNN

• Autorzy: Szyprowski M. , Kerntopf P.

Warianty tytułu

EN

Designing reversible circuits in the LNN architecture

• Języki publikacji: PL

Abstrakty

PL

Najnowszy kierunek w projektowaniu kwantowych układów odwracalnych uwzględnia fakt, że interakcje odbywają się tylko na sąsiadujących liniach. Ostatnio zaproponowano wiele algorytmów projektowania takich układów oraz zajmowano się ich optymalizacją. W pracy przedstawiony jest przegląd tych rozwiązań oraz perspektywy rozwoju tej ważnej dziedziny.

EN

Computation is called reversible if it is realized by circuits implementing bijective mappings. It is an emerging research area which 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 low power computation. Quantum computation, which by nature is reversible, constitutes an especially attractive field of research due to a promise of an enormous speed-up of computing processes in the future. However, it has appeared that in some quantum technologies there are intrinsic limitations, namely, physically realizable operations would be only interactions between neighbor lines (also called qubits). As reversible circuits form a subset of quantum circuits there is a need to convert general reversible circuits into the so-called Linear Nearest Neighbor (LNN) architecture. In this architecture any gate operates between adjacent qubits only. Thus, recently there has been a new research objective to develop efficient methods for designing reversible circuits in the LNN architecture. This paper gives an overview of the present advances in this field.

Słowa kluczowe

PL

układy odwracalne; układy kwantowe; architektura LNN

EN

reversible circuits; quantum circuits; LLN architecture

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2013
• Tom: R. 59, nr 8
• Strony: 781--783
• Opis fizyczny: Bibliogr. 25 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.

• Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej, ul. Pomorska149/153, 90-236 Łódź

Bibliografia

• [1] De Vos A.: Reversible Computing. Fundamentals, Quantum Computing and Applications. Wiley-VCH, Berlin 2010.
• [2] Kerntopf P.: Synteza odwracalnych układów logicznych. Pomiary Automatyka Kontrola, vol. 53, s. 78-80, 2007.
• [3] Szyprowski M., Kerntopf P.: Decompositions of reversible logic circuits. Pomiary Automatyka Kontrola, vol. 55, s. 609-611, 2009.
• [4] Zagniński P., Kerntopf P.: Sekwencyjne odwracalne układy logiczne. Pomiary Automatyka Kontrola, vol. 56, s. 678-680, 2010.
• [5] Szyprowski M., Kerntopf P.: Realizacje układów odwracalnych w technologiach półprzewodnikowych. Pomiary Automatyka Kontrola, vol. 57, s. 911-813, 2011.
• [6] Szyprowski M., Kerntopf P.: Odwracalne układy programowalne. Pomiary Automatyka Kontrola, vol. 58, s. 644-646, 2012.
• [7] Quantum Computation Roadmap. Los Alamos National Laboratory, http://qist.lanl.gov/qcomp_map.shtml, 2004.
• [8] Saeedi M., Markov I. L.: Synthesis and optimization of reversi-ble circuits – a survey. ACM Computing Surveys, vol. 45, no. 2, article 21, s. 1-34, 2013.
• [9] Fowler A. G., Devitt S. J., Hollenberg L. C.: Implementation of Shor’s algorithm on a linear neighbour qubit array. Quantum Information and Computation, vol. 4, s. 237-245, 2004.
• [10] Fowler A. G., Hill C. D., Hollenberg L. C.: Quantum error correction on linear nearest neighbor qubit arrays. Physical Review A, vol. 69, s. 042314.1-042314.4, 2004.
• [11] Shende V., Bullock S., Markov I. L.: Synthesis of quantum logic cir-cuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, s. 1000-1010, 2006.
• [12] Takahashi Y., Kunihiro N., Ohta K.: The quantum Fourier transform on a linear nearest architecture. Quantum Information and Computation, vol. 7, s. 383-391, 2007.
• [13] Kutin S. A.: Shor’s algorithm on a nearest-neighbor machine. Proceedings of the Asian Conference on Quantum Information Science, s. 12-13, 2007.
• [14] Cheung D., Maslov D., Severini S.: Translation techniques between quantum circuit architectures. Proceedings of the Workshop on Quantum Information Processing, s. 1-3, 2007.
• [15] Maslov D.: Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Physical. Review A, vol. 76, s. 052310.1-052310.7, 2007.
• [16] Chakrabarti A., Sur-Kolay S.: Rules for synthesizing quantum boolean circuits using minimized nearest-neighbour templates. Proceedings of the International Conference on Advanced Computing and Communications, s. 183–189, 2007.
• [17] Chakrabarti A., Sur-Kolay S.: Nearest neighbour based synthesis of quantum boolean circuits. Engineering Letters, vol. 15, s. 356–361, 2007.
• [18] Khan M. H. A.: Cost reduction in nearest neighbour based synthesis of quantum boolean circuits. Engineering Letters, vol. 16, s. 1–5, 2008.
• [19] Choi B.S., Van Meter R.: Effects of interaction distance on quantum addition circuits. arXiv:0809.4317, 2008.
• [20] Saeedi M., Wille R., Drechsler R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Information Processing, vol. 10, s. 355-377, 2011.
• [21] Hirata Y., Nakanishi M., Yamashita S., Nakashima Y.: An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quantum Information and Computation, vol. 11, s. 142-166, 2011.
• [22] Perkowski M., Lukac M., Shah D., Kameyama M.: Synthesis of quantum circuits in linear nearest neighbor model using positive Davio lattices. Facta Universitatis, Series: Electronics and Energetics, vol. 24, s. 73-89, 2011.
• [23] Rahman M.M., Dueck G.W.: Synthesis of linear nearest neighbor quantum circuits. Proceedings of the 11th International Workshop on Boolean Problems, s. 277-284, 2012.
• [24] Matsuo A., Yamashita S.: Changing the gate order for optimal LNN conversion. A. De Vos, R. Wille (eds.) Reversible Computation, vol. 7165, s. 89-101, Springer-Verlag, Berlin Heidelberg, 2012.
• [25] Rosenbaum D.: Optimal quantum circuits for nearest-neighbor architectures. arXiv:1205.0036, 2012.