Extending scientific computing system with structural quantum programming capabilities

• Autorzy: Gawron P. , Klamka J. , Miszczak J. , Winiarczyk R.
• Języki publikacji: EN

Abstrakty

EN

We present the basic high-level structures used for developing quantum programming languages. The presented structures are commonly used in many existing quantum programming languages and we use quantum pseudo-code based on QCL quantum programming language to describe them. We also present the implementation of introduced structures in GNU Octave language for scientific computing. Procedures used in the implementation are available as a package quantum-octave providing library of functions, which facilitates the simulation of quantum computing. This package allows also to incorporate high-level programming concepts into the simulation in GNU Octave and Matlab. As such it connects features unique for higl-level quantum programming languages, with the full palette of efficient computational routines commonly available in modern scientific computing systems. To present the major features of the described package we provide the implementation of selected quantum algorithms. We also show how quantum errors can be taken into account during the simulation of quantum algorithms using quantum-octave package. This is possible thanks to the ability to operate on density matrices implemented in quantum-octave.

Słowa kluczowe

EN

quantum information; quantum programming; models of quantum computation

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2010
• Tom: Vol. 58, nr 1
• Strony: 77--88
• Opis fizyczny: Bibliogr. 38 poz., rys.

Twórcy

autor

Gawron P.

autor

Klamka J.

autor

Miszczak J.

autor

Winiarczyk R.

• Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, 5 Bałtycka St., 44-100 Gliwice, Poland,

Bibliografia

• [1] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000.
• [2] M. Hirvensalo, Quantum Computing, Springer, Berlin, 2001.
• [3] S. Bugajski, J. Klamka, and S. Wegrzyn, “Foudations of quantum computing, Part I”, Archives of Theoretical and Applied Informatics 13 (1), 97–142 (2001), (in Polish).
• [4] S. Bugajski, J. Klamka, and S. Wegrzyn, “Foudations of quantum computing. Part II”, Archives of Theoretical and Applied Informatics 13 (1), 137–149 (2001), (in Polish).
• [5] P.W. Shor, “Why haven’t more quantum algorithms been found?”, ACM 50 (1), 87–90 (2003).
• [6] P.W. Shor, “Progress in quantum algorithms”, Quantum Information Processing 3, 1–5 (2004).
• [7] D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer”, Proc. Roy. Soc. Lond. A 400, 97 (1985).
• [8] D. Deutsch, “Quantum computational networks”, Proc. Roy. Soc. Lond. A 425, 73 (1989).
• [9] S. Bettelli, L. Serafini, and T. Calarco, “Toward an architecture for quantum programming”, Eur. Phys. J. D 25 (2), 181–200 (2003).
• [10] S. Gudder, “Quantum computational logic”, Int. J. Theoretical Physics 1 (42), 39–47 (2003).
• [11] A. van Tonder, “A lambda calculus for quantum computation”, SIAM J.COMPUT. 33, 1109 (2004).
• [12] C. Moore and J.P. Crutchfield, “Quantum automata and quantum grammars”, Theoretical Computer Science 237 (1–2), 275–306 (2000).
• [13] E. Bernstein and U. Vazirani, “Quantum complexity theory”, SIAM J. on Computing 26 (5), 1411–1473 (1997).
• [14] S. Gay, “Quantum programming languages: Survey and bibliography”, Bull. Eur. Association for Theoretical Computer Science 1, CD-ROM (2005).
• [15] J.A.Miszczak, Probabilistic Aspects of Quantum Programming Languages, PhD Thesis, The Institute of Theoretical and Applied Informatics PAS, Warsaw, 2008.
• [16] S. Gay, Bibliography on Quantum Programming Languages, web-page http://www.dcs.gla.ac.uk/˜simon/quantum/, 2007.
• [17] T. Altenkirch and J. Grattage, “A functional quantum programming language”, Proc. Annual IEEE Symposium on Logic in Computer Science 1, 249–258 (2005).
• [18] E. Knill, “Conventions for quantum pseudocode”, Technical Report LAUR-96-2724 1, CD-ROM (1996).
• [19] B. Oeme, Structured Quantum Programming, PhD Thesis, Technical University of Vienna, Vienna, 2003.
• [20] S.A. Cook and R.A. Reckhow, “Time-bounded random access machines”, Proc. forth Annual ACM Symposium on Theory of Computing 1, 73–80 (1973).
• [21] C.H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, New York, 1994.
• [22] J.C. Shepherdson and H.E. Strugis, “Computability of recursive functions”, J. ACM 10 (2), 217–255 1963.
• [23] R. Cleve and D.P. DiVincenzo, “Schumacher’s quantum data compression as a quantum computation”, Phys. Rev. A 54 (4), 2636–2650 (1996).
• [24] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, The MIT Press, London, 2001.
• [25] J.E. Hopcroft and J.D. Ullman, Introduction to the Theory of Automata, Language, PWN Scientific Publishing House, Warsaw, 2003, (in Polish).
• [26] S. Bettelli, Toward an Architecture for Quantum Programming, PhD Thesis, Universit`a di Trento, Trento, 2002.
• [27] P. Gawron, High Level Programming in Quantum Computer Science, PhD Thesis, The Institute of Theoretical and Applied Informatics PAS, Warsaw, 2008.
• [28] B. Oemer, Quantum Programming in QCL, Master Thesis, TU Viena, Vienna, 2000.
• [29] P. Gawron and J.A. Miszczak, “Didactic tools for teaching quantum informatics”, Annales UMCS Informatica AI 1 (2), 77–79 (2004).
• [30] P. Gawron and J.A. Miszczak, “Simulations of quantum systems evolution with quantum-octave package”, Annales UMCS Informatica AI 1 (2), 52–63 (2004).
• [31] P. Gawron and J.A. Miszczak, “Numerical simulations of mixed states quantum computation”, Int. J. Quan. Inf. 3 (1), 195–199 (2005).
• [32] J.W. Eaton, GNU Octave Manual, Network Theory Limited, New York, 2002.
• [33] L. Grover, “A fast quantum mechanical algorithm for database search”, Proc. 28th Annual ACM Symposium on the Theory of Computation 1, 212–219 (1996).
• [34] L.K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Phys. Rev. Lett. 79, 325 (1997).
• [35] L.K. Grover, “A framework for fast quantum mechanical algorithms”, Proc. 30th Annual ACM Symposium on Theory of Computing (STOC) 1, 53–62 (1998).
• [36] S. Bugajski, “Quantum search”, Archives of Theoretical and Applied Informatics 13 (2), 143–150 (2001).
• [37] S.J. Lomonaco, “Grover’s quantum search algorithm”, Proc. Symposia in Applied Mathematics 58, 181–192 (2002).
• [38] Project quantum-octave, http://quantum-octave.sf.net/, 2007.