Models of quantum computation and quantum programming languages

Miszczak, J.

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!

Artykuł - szczegóły

Tytuł artykułu

Models of quantum computation and quantum programming languages

Autorzy

Miszczak J.

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

Warianty tytułu

Języki publikacji

Abstrakty

The goal of the presented paper is to provide an introduction to the basic computational models used in quantum information theory. We review various models of quantum Turing machine, quantum circuits and quantum random access machine (QRAM) along with their classical counterparts. We also provide an introduction to quantum programming languages, which are developed using the QRAM model. We review the syntax of several existing quantum programming languages and discuss their features and limitations.

Słowa kluczowe

programming languages models of computation Turing machine

Wydawca

Polska Akademia Nauk, Wydział IV Nauk Technicznych

Czasopismo

Bulletin of the Polish Academy of Sciences. Technical Sciences

Rocznik

2011

Tom

Vol. 59, nr 3

Strony

305--324

Opis fizyczny

Bibliogr. 98 poz., rys., tab.

Twórcy

autor

Miszczak J.

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

Bibliografia

[1] D. Bouwmeester, A. Ekert, and A. Zeilinger, The Physics of Quantum Information: Quantum Cryptography, Quantum Teleportation, Quantum Computation, Springer-Verlag, Berlin, 2000.
[2] T. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. O’Brien, “Quantum computers”, Nature 464, 45–53 (2010).
[3] G.E. Moore, “Cramming more components onto integrated circuits”, Electronics 38 (8), 114–117 (1965).
[4] Intel Corporation, Moores Law: Intel Microprocessor Transistor Count Chart, http://intel.com/pressroom/kits/events/moores law 40th/ (2005).
[5] R.P. Feynman, “Simulating physics with computers”, Int. J. Theor. Phys. 21 (6/7), 467–488 (1982).
[6] C.H. Bennett and G. Brassard, “Quantum cryptography: public key distribution and coin tossing”, Proc. IEEE Int. Conf. on Computers, Systems, and Signal Processing 1, 175–179 (1984).
[7] A. Ekert, “Quantum cryptography based on Bell’s theorem”, Phys. Rev. Lett. 67, 661–663 (1991).
[8] A. Einstein, B. Podolsky, and N. Rosen, “Can quantummechanical description of physical reality be considered complete?”, Phys. Rev. 47 (10), 777–780 (1935).
[9] J. Bouda, “Encryption of quantum information and quantum cryptographic protocols”, Ph.D. Thesis, Faculty of Informatics, Masaryk University, Brno, 2004.
[10] R. Ursin, F. Tiefenbacher, T. Schmitt-Manderbach, H. Weier, T. Scheidl, M. Lindenthal, B. Blauensteiner, T. Jennewein, J. Perdigues, P. Trojek, B. ¨Omer, M. F¨urst, M. Meyenburg, J. Rarity, Z. Sodnik, C. Barbieri, H. Weinfurter, and A. Zeilinger, “Entanglement-based quantum communication over 144 km”, Nature Physics 3, 481–486 (2007).
[11] M. Peev, C. Pacher, R. All´eaume, C. Barreiro, J. Bouda, W. Boxleitner, T. Debuisschert, E. Diamanti, M. Dianati, J.F. Dynes, S. Fasel, S. Fossier, M. F¨urst, J.D. Gautier, O. Gay, N. Gisin, P. Grangier, A. Happe, Y. Hasani, M. Hentschel, H. Hubel, G. Humer, T. L¨anger, M. Legr´e, R. Lieger, J. Lodewyck, T. Lor¨unser, N. L¨utkenhaus, A. Marhold, T. Matyus, O. Maurhart, L. Monat, S. Nauerth, J.B. Page, A. Poppe, E. Querasser, G. Ribordy, S. Robyr, L. Salvail, A.W. Sharpe, A.J. Shields, D. Stucki, M. Suda, C. Tamas, T. Themel, R.T. Thew, Y. Thoma, A. Treiber, P. Trinkler, R. Tualle-Brouri, 322 Bull. Pol. Ac.: Tech. 59(3) 2011 Models of quantum computation and quantum programming languages F. Vannel, N. Walenta, H. Weier, H. Weinfurter, I. Wimberger, Z.L. Yuan, H. Zbinden, and A. Zeilinger, “The SECOQC quantum key distribution network in Vienna”, New J. Physics 11 (7), 075001 (2009).
[12] P.W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring”, Proc. 35th Annual Symposium on Foundations of Computer Science 1, 124–134 (1994).
[13] P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computers”, SIAM J. Computing 26, 1484–1509 (1997).
[14] L.K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Phys. Rev. Lett. 79, 325–328 (1997).
[15] J. Eisert, M. Wilkens, and M. Lewenstein, “Quantum games and quantum strategies”, Phys. Rev. Lett. 83, 3077–3080 (1999).
[16] D. Meyer, AMS Contemporary Mathematics: Quantum Computation and Quantum Information Science, vol. 305, American Mathematical Society, Rhode Island, 2000.
[17] J. Kempe, “Quantum random walks: an introductory overview”, Contemp. Phys. 44 (4), 307–327 (2003).
[18] J. Koˆs´ık, “Two models of quantum random walk”, Cent. Eur. J. Phys. 4, 556–573 (2003).
[19] P. W. Shor, “Progress in quantum algorithms”, Quantum Information Processing 3, 1–5 (2004).
[20] S.J. Lomonaco and L. Kauffman, “Search for new quantum algorithms”, Tech. Rep. F30602-01-2-0522, http://www.cs.umbc.edu/lomonaco/qis/DARPA-FINAL-RPT.pdf, (2005).
[21] E. Bernstein and U. Vazirani, “Quantum complexity theory”, SIAM J. Computing 26 (5), 1411–1473 (1997).
[22] L. Fortnow, “One complexity theorist’s view of quantum computing”, Theor. Comput. Sci. 292 (3), 597–610 (2003).
[23] E. Klarreich, “Playing by quantum rules”, Nature 414, 244–245 (2001).
[24] C.F. Lee and N.F. Johnson, “Game-theoretic discussion of quantum state estimation and cloning”, Phys. Lett. A 319 (5–6), 429–433 (2003).
[25] A. Ambainis, “Quantum walk algorithm for element distinctness”, SIAM J. Computing 37, 210–239 (2007).
[26] A.M. Childs and J.M. Eisenberg, “Quantum algorithms for subset finding”, Quantum. Inf. Comput. 5, 593 (2005).
[27] A.M. Childs and J. Goldstone, “Spatial search by quantum walk”, Phys. Rev. A 70 (2), 022314.1 (2004).
[28] A.M. Childs, “Universal computation by quantum walk”, Phys. Rev. Lett. 102 (18), 180501 (2009).
[29] A.P. Hines and P.C.E. Stamp, “Quantum walks, quantum gates, and quantum computers”, Phys. Rev. A 75 (6), 062321 (2007).
[30] A. Ambainis, “Quantum walks and their algorithmic applications”, Int. J. Quant. Inf. 1, 507–518 (2003).
[31] M. Santha, “Quantum walk based search algorithms”, 5th Theory and Applications of Models of Computation 4978, 31–46 (2008).
[32] S.E. Venegas-Andraca, “Introduction to special issue: physics and computer science – quantum computation and other approaches”, Math. Struct. Comp. Sci. 20 (6), 995–997 (2010).
[33] M. Mosca and J. Smith, “Algorithms for quantum computers”, in: Handbook of Natural Computing, Springer Verlag, Berlin, 2011.
[34] A. Childs and W. van Dam, “Quantum algorithms for algebraic problems”, Rev. Mod. Phys. 82 (1), 1–52 (2010).
[35] C.H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, London, 1994.
[36] 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).
[37] J.C. Shepherdson and H.E. Strugis, “Computability of recursive functions”, J. ACM 10 (2), 217–255 (1963).
[38] H. Vollmer, Introduction to Circuit Complexity, Springer-Verlag, Berlin, 1999.
[39] A. Church, “An unsolvable problem of elementary number theory”, American J. Mathematics 58, 345–363 (1936).
[40] H. Abelson, G.J. Sussman, and J. Sussman, Structure and Interpretation of Computer Programs, MIT Press, Cambridge, 1996.
[41] J.C. Mitchell, Concepts in Programming Languages, Cambridge University Press, Cambridge, 2003.
[42] D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer”, Proc. R. Soc. Lond. A 400, 97 (1985).
[43] C. Bohm, “On a family of Turing machines and the related programming language”, ICC Bull. 3, 187–194 (1964).
[44] S. Aaronson and G. Kuperberg, “Complexity Zoo”, http://qwiki.stanford.edu/index.php/Complexity Zoo, (2010).
[45] A. Yao, “Quantum circuit complexity”, Proc. 34th IEEE Symposium on Foundations of Computer Science 1, 352–360 (1993).
[46] H. Nishimura and M. Ozawa, “Computational complexity of uniform quantum circuit families and quantum Turing machines”, Theor. Comput. Sci. 276, 147–181 (2002).
[47] U. Vazirani, “A survey of quantum complexity theory”, Proc. Sympos. Appl. Math. 1, 58 (2002).
[48] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, W.H. Freeman, London, 1979.
[49] U. Zwick, “Scribe notes of the course Boolean circuit complexity”, http://www.cs.tau.ac.il/∼zwick/scribe-boolean.html, (1995).
[50] M. Hirvensalo, Quantum computing, Springer-Verlag, Berlin, 2001.
[51] D. Deutsch, “Quantum computational networks”, Proc. R. Soc. Lond. A 425, 73 (1989).
[52] T. Toffoli, “Bicontinuous extension of reversible combinatorial functions”, Math. Syst. Theory 14, 13–23 (1981).
[53] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000.
[54] A. Barenco, C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter, “Elementary gates for quantum computation”, Phys. Rev. A 52, 3457 (1995).
[55] D. Deutsch, A. Barenco, and A. Ekert, “Universality in quantum computation”, Proc. R. Soc. Lond. 1, 449 (1937), 669–677 (1995).
[56] V.V. Shende, I.L. Markov, and S.S. Bullock, “Minimal universal two-qubit controlled-NOT-based circuits”, Phys. Rev. A 69, 062321 (2004).
[57] M. M¨ott ¨onen, J.J. Vartiainen, V. Bergholm, and M.M. Salomaa, “Quantum circuits for general multiqubit gates”, Phys. Rev. Lett. 93 (13), 130502 (2004).
[58] J.J. Vartiainen, M. Mottonen, and M.M. Salomaa, “Efficient decomposition of quantum gates”, Phys. Rev. Lett. 92, 177902 (2004).
[59] S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits”, Phys. Rev. A 70 (5), 052328 (2004).
[60] E. Knill, “Conventions for quantum pseudocode”, Tech. Rep. LAUR-96-2724, CD-ROM (1996).
[61] B. ¨Omer, “Structured quantum programming”, Ph.D. Thesis, Vienna University of Technology, Vienna, 2003.
[62] R. Nagarajan, N. Papanikolaou, and D. Williams, “Simulating and compiling code for the sequential quantum random access machine”, Electronic Notes in Theoretical Computer Science 170, 101–124 (2007).
[63] R. Cleve and D.P. DiVincenzo, “Schumacher’s quantum data compression as a quantum computation”, Phys. Rev. A 54 (4), 2636–2650 (1996).
[64] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, London, 2001.
[65] K.M. Svore, A.W. Cross, A.V. Aho, I.L. Chuang, and I.L. Markov, “Toward a software architecture for quantum computing design tools”, Proc. 2nd Int. Workshop on Quantum Programming Languages 1, CD-ROM (2004).
[66] K.M. Svore, A.W. Cross, I.L. Chuang, A.V. Aho, and I.L. Markov, “A layered software architecture for quantum computing design tools”, Computer 39 (1), 74–83 (2006).
[67] S. Bettelli, “Toward an architecture for quantum programming”, Ph.D. Thesis, Universit`a di Trento, Trente, 2002.
[68] L.K. Grover, “Quantum computers can search rapidly by using almost any transformation”, Phys. Rev. Lett. 80, 4329–4332 (1998).
[69] M. Mosca, “Quantum computer algorithms”, Ph.D. Thesis, Wolfson College, University of Oxford, Oxford, 1999.
[70] C. Bennett and S. Wiesner, “Communication via one- and twoparticle operators on Einstein-Podolsky-Rosen states”, Phys. Rev. Lett. 69, 2881–2884 (1992).
[71] G. Brassard, A. Broadbent, and A. Tapp, “Quantum pseudotelepathy”, Found. Phys. 35, 1877–1907 (2005).
[72] D. Bacon and W. van Dam, “Recent progress in quantum algorithms”, Commun. ACM 53 (2), 84–93 (2010).
[73] E.H. Knill and M.A. Nielsen, Encyclopedia of Mathematics, Supplement, Kluwer, London, 2002.
[74] S. Bettelli, L. Serafini, and T. Calarco, “Toward an architecture for quantum programming”, Eur. Phys. J. D 25 (2), 181–200 (2003).
[75] W. Mauerer, “Semantics and simulation of communication in quantum programming”, Master’s Thesis, University Erlangen-Nuremberg, Nuremberg, 2005.
[76] H. Mlnaˇr´ık, “Operational semantics and type soundness of quantum programming language LanQ”, Ph.D. Thesis, Masaryk University, Brno, 2007.
[77] H. Mlnaˇr´ık, “Semantics of quantum programming language LanQ”, Int. J. Quant. Inf. 6 (1, Supp.), 733–738 (2008).
[78] S. Gay, “Quantum programming languages: survey and bibliography”, Math. Struct. Comput. Sci. 16 (4), CD-ROM (2006).
[79] D. Unruh, “Quantum programming languages”, Informatik – forschung und entwicklung 21 (1–2), 55–63 (2006).
[80] R. R¨udiger, “Quantum programming languages: an introductory overview”, Comput. J. 50 (2), 134–150 (2007).
[81] B. ¨Omer, “A procedural formalism for quantum computing”, Master’s Thesis, Vienna University of Technology, Vienna, 1998.
[82] B. ¨Omer, “Quantum programming in QCL”, Master’s Thesis, Vienna University of Technology, Vienna, 2000.
[83] H. Weimer, The C Library for Quantum Computing and Quantum Simulation Version 1.1.0, http://www.libquantum.de/ (2010).
[84] S. Bettelli, L. Serafini, and T. Calarco, “Toward an architecture for quantum programming”, Eur. Phys. J. D 25 (2), 181–200 (2003).
[85] J.A. Miszczak and P. Gawron, “Numerical simulations of mixed states quantum computation”, Int. J. Quant. Inf. 3 (1), 195–199 (2005).
[86] P. Gawron, J. Klamka, J. Miszczak, and R. Winiarczyk, “Extending scientic computing system with structural quantum programming capabilities”, Bull. Pol. Ac.: Tech. 58 (1), 77–88 (2010).
[87] H. Mlnaˇr´ık, “LanQ – Operational semantics of quantum programming language LanQ”, Tech. Rep. FIMU-RS-2006-10, Masaryk University, Brno, 2006.
[88] A. van Tonder, “A lambda calculus for quantum computation”, SIAM J. Comput. 33 (5), 1109–1135 (2004).
[89] P. Selinger, “Towards a quantum programming language”, Math. Struct. Comput. Sci. 14 (4), 527–586 (2004).
[90] B.W. Kernighan and D.M. Ritchie, C Programming Language, Prentice Hall, Upper Saddle River, 1988.
[91] D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation”, Proc. Roy. Soc. Lond. A 439, 553–558 (1992).
[92] W.K. Wootters and W.H. Zurek, “A single quantum cannot be cloned”, Nature 299, 802–803 (1982).
[93] V. Vedral, A. Barenco, and A. Ekert, “Quantum networks for elementary arithmetic operations”, Phys. Rev. A 54, 147–153 (1996).
[94] P. Selinger, “A brief survey of quantum programming languages”, Proc. 7th Int. Symposium on Functional and Logic Programming 2998 of LNCS 1, 1–6 (2004).
[95] J. Hughes, “Why functional programming matters”, Comput. J. 32 (2), 98–107 (1989).
[96] A. Sabry, “Modeling quantum computing in Haskell”, ACM SIGPLAN Haskell Workshop 1, CD-ROM (2002).
[97] J. Karczmarczuk, “Structure and interpretation of quantum mechanics: a functional framework”, Proc. ACM SIGPLAN Workshop on Haskell 1, 50–61 (2003).
[98] G. Hutton, Programming in Haskell, Cambridge University Press, Cambridge, 2007.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BPG8-0070-0019