Software for Quantum systems of Informatics

• Autorzy: Francik, J.
• Języki publikacji: EN

Abstrakty

EN

The paper is an attempt to look quantum information techniques from the perspective of a software engineer. In background some key concepts that affect quantum algorithm construction have been introduced. Several quantum algorithms have been presented, Grover's search and Shor's factorization among them, using classical software engineering methods: high-level pseudocodes and programming languages, schemas, software visualization. It is also analyzed how the specifics of quantum mechanics has to affect these means of description.

PL

Artykuł jest próbą spojrzenia na kwantowe techniki informatyczne z perspektywy inżynierii oprogramowania. Przedstawiono kluczowe koncepcje, które mają wpływ na konstrukcję algorytmów kwantowych. Podjęto próbę przedstawienia wybranych algorytmów ( w tym wyszukiwania Grovera i faktoryzacji Shora) za pomocą klasycznych, informatycznych środków opisu: pseudokodu, języka programowania wysokiego poziomu, wizualizacji oprogramowania. Przeanalizowano, w jaki sposób specyfika mechaniki kwantowej musi wpłynąć na tego typu środki opisu.

• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2003
• Tom: T. 15, z. 3
• Strony: 187-205
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Francik, J.

• Instytut Informatyki. Politechnika Śląska, ul. Akademicka 16, 44-100 Gliwice, Poland

Bibliografia

• [1]Benioff P. A.: Quantum mechanical Hamiltonian models of Touring machines. Journal of Statistical Physics, 29(3), 1982. pp. 515-546.
• [2] Boyer M., Brassard G., Hoyer P., Tapp A.: Tight bounds on quantum searching, manuscript quant - ph/9605034, 1996.
• [3] Brassard G..,Hoyer P., Tapp A., Quantum counting. Proc. of 25th International Colloquium on Automata, Languages, and Programming (ICALP'98), Vol. 1443 of Lecture Notes in Computer Science, pp. 820-831, 1998.
• [4] Bugajski S., Klamka J., Węgrzyn S.: Foundations of Quantum Computing. Part I. Archiwum Informatyki Teoretycznej i Stosowanej. Vol. 13 No 2/2001. pp. 96-142.
• [5] Bugajski S.: Quantum Serach. Archiwum Informatyki Teoretycznej i Stosowanej, Vol. 13 No 2/2001, pp. 143-150.
• [6] Colwel B.: Engineering, Science and Quantum Mechanics. IEEE Comp. 35/2002. pp. 8-10.
• [7] D. Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research Report RC 19642 (1904).
• [8] Cormen T. H., Leiserson C. E., Rivest R. L.: Introduction to Algorithms. Polish edition: WNT. Warszawa 1997.
• [9] Deutsch D., Jozsa R.: Rapid solutions of problems by quantum computation. Proc. of the Royal Society. London, 1992.
• [10] Dtirr C., Hoyer P.: A quantum algorithm for finding the minimum. Technical report of University of Paris-Stid and University of Odense, 1996.
• [11] . Francik J.: Quantum Software. Seminarium Sieci Komputerowe, Zakopane 2002. Studia Informatica Vol. 23 No 2A(48), pp. 113-120.
• [12] Francik J.: Algorithm Animation Using Data Flow Tracing. In: S. Diehl (Ed.): Software Visualization. LNCS 2269. Springer Verlag, 2002. pp. 73-87.
• [13] Gershenfeld N.. Chuang I. L: Quantum Computing with Molecules, Scientific American, June 1998 (reprinted in Polish in Świat Nauki No 8/1998).
• [14] Grover L. K.: A Fast Quantum Mechanical Algorithm for Database Search. Proc of STOC 1996, Philadelphia PA (ACM Press New York), pp. 212-219.
• [15] Hovland T.: Quantum Computation in a Global Pulse Driven Framework. PhD thesis. National University or Ireland, Maynooth, 2001,
• [16] http://planck.thphys.may.ie/jtwamley/thesis/Hovland/thesis
• [17] Klamka J.: Quantum search algorithm. Seminarium Sieci Komputerowe, Zakopane 2002.
• [18] Koskela J -P., Mettinen K.: Why do quantum algorithms work? (Deutsch-Josza problem). Quantum Computing. Dept, of Comp. Science, Univ. of Helsinki 1998.
• [19] Lecerf Y. : Machines de Touring réversibles. Recursive insolubilité en n € N de l’équation u = 0“ où 0 est un isomorphisme de codes. Comptes rendus de l'Académie française des sciences, 257. 1963, pp. 2597-2600.
• [20] Orner B.: Quantum Programming in QCL. PhD thesis. Institute of Inf. Systems, Technical University of Vienna. Austria 2000.
• [21] R L. Rivest, A. Shamir, L. M. Adleman: A method for obtaining digital signatures and public-key cryptosystems. Comm, of the ACM, 21(2): 120-126. 1978. Also: U.S. Patent 4,405.829.
• [22] Shor P. W., : Algorithms for Quantum Computation: Discrete Logarithms and Factoring. IEEE Sympo¬sium on Foundations of Computer Science, Santa Fe. 1994, IEEE Comp. Society Press, pp. 124-134.
• [23] Trybicka-Francik K., Francik J : Klasyczna i kwantowa faktoryzacja liczb w kryptografii z. kluczem jawnym (Classical and quantum factorization in public key cryptography). Int. Conf. Information and Communication Technology Security. Biclsko-Biala 2003. vol. 1. pp. 39-49.
• [24] Węgrzyn A., Klamka J.: Quantum Systems of Informatics, IITiS PAN. Gliwice 2000.