Title

Models of quantum computation and quantum programming languages

Journal title

Bulletin of the Polish Academy of Sciences Technical Sciences

Yearbook

2011

Volume

59

Issue

No 3

Authors

Miszczak, J.

Divisions of PAS

Nauki Techniczne

Coverage

305-324

Date

2011

Identifier

DOI: 10.2478/v10175-011-0039-5 ; ISSN 2300-1917

Source

Bulletin of the Polish Academy of Sciences: Technical Sciences; 2011; 59; No 3; 305-324

References

Bouwmeester D. (2000), The Physics of Quantum Information: Quantum Cryptography, Quantum Teleportation, Quantum Computation. ; Ladd T. (2010), Quantum computers, Nature, 464, 45, doi.org/10.1038/nature08812 ; Moore G. (1965), Cramming more components onto integrated circuits, Electronics, 38, 8, 114. ; Intel Corporation, <i>Moores Law: Intel Microprocessor Transistor Count Chart</i> <a target="_blank" href='http://intel.com/pressroom/kits/events/moores_law_40th/'>http://intel.com/pressroom/kits/events/moores_law_40th/</a> ; Feynman R. (1982), Simulating physics with computers, Int. J. Theor. Phys, 21, 6/7, 467, doi.org/10.1007/BF02650179 ; Bennett C. (1984), Quantum cryptography: public key distribution and coin tossing, Proc. IEEE Int. Conf. on Computers, Systems, and Signal Processing, 1, 175. ; Ekert A. (1991), Quantum cryptography based on Bell's theorem, Phys. Rev. Lett, 67, 661, doi.org/10.1103/PhysRevLett.67.661 ; Einstein A. (1935), Can quantummechanical description of physical reality be considered complete?, Phys. Rev, 47, 10, 777, doi.org/10.1103/PhysRev.47.777 ; J. Bouda, "Encryption of quantum information and quantum cryptographic protocols", <i>Ph.D. Thesis</i>, Faculty of Informatics, Masaryk University, Brno, 2004. ; Ursin R. (2007), Entanglement-based quantum communication over 144 km, Nature Physics, 3, 481, doi.org/10.1038/nphys629 ; Peev M. (2009), The SECOQC quantum key distribution network in Vienna, New J. Physics, 11, 7, 075001, doi.org/10.1088/1367-2630/11/7/075001 ; Shor P. (1994), Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th Annual Symposium on Foundations of Computer Science, 1, 124, doi.org/10.1109/SFCS.1994.365700 ; Shor P. (1997), Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computers, SIAM J. Computing, 26, 1484, doi.org/10.1137/S0097539795293172 ; Grover L. (1997), Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett, 79, 325, doi.org/10.1103/PhysRevLett.79.325 ; Eisert J. (1999), Quantum games and quantum strategies, Phys. Rev. Lett, 83, 3077, doi.org/10.1103/PhysRevLett.83.3077 ; Meyer D. (2000), AMS Contemporary Mathematics: Quantum Computation and Quantum Information Science, 305. ; Kempe J. (2003), Quantum random walks: an introductory overview, Contemp. Phys, 44, 4, 307, doi.org/10.1080/00107151031000110776 ; Koŝík J. (2003), Two models of quantum random walk, Cent. Eur. J. Phys, 4, 556, doi.org/10.2478/BF02475903 ; Shor P. (2004), Progress in quantum algorithms, Quantum Information Processing, 3, 1, doi.org/10.1007/s11128-004-3878-2 ; S.J. Lomonaco and L. Kauffman, "Search for new quantum algorithms", <i>Tech. Rep.</i> F30602-01-2-0522 <a target="_blank" href='http://www.cs.umbc.edu/lomonaco/qis/DARPA-FINAL-RPT.pdf'>http://www.cs.umbc.edu/lomonaco/qis/DARPA-FINAL-RPT.pdf</a> ; Bernstein E. (1997), Quantum complexity theory, SIAM J. Computing, 26, 5, 1411, doi.org/10.1137/S0097539796300921 ; Fortnow L. (2003), One complexity theorist's view of quantum computing, Theor. Comput. Sci, 292, 3, 597, doi.org/10.1016/S0304-3975(01)00377-2 ; Klarreich E. (2001), Playing by quantum rules, Nature, 414, 244, doi.org/10.1038/35104702 ; Lee C. (2003), Game-theoretic discussion of quantum state estimation and cloning, Phys. Lett, A 319, 5-6, 429, doi.org/10.1016/j.physleta.2003.10.019 ; Ambainis A. (2007), Quantum walk algorithm for element distinctness, SIAM J. Computing, 37, 210, doi.org/10.1137/S0097539705447311 ; Childs A. (2005), Quantum algorithms for subset finding, Quantum. Inf. Comput, 5, 593. ; Childs A. (2004), Spatial search by quantum walk, Phys. Rev, A 70, 2. ; Childs A. (2009), Universal computation by quantum walk, Phys. Rev. Lett, 102, 18, 180501, doi.org/10.1103/PhysRevLett.102.180501 ; Hines A. (2007), Quantum walks, quantum gates, and quantum computers, Phys. Rev, A 75, 6, 062321. ; Ambainis A. (2003), Quantum walks and their algorithmic applications, Int. J. Quant. Inf, 1, 507, doi.org/10.1142/S0219749903000383 ; Santha M. (2008), Quantum walk based search algorithms, 5th Theory and Applications of Models of Computation, 4978, 31, doi.org/10.1007/978-3-540-79228-4_3 ; Venegas-Andraca S. (2010), Introduction to special issue: physics and computer science - quantum computation and other approaches, Math. Struct. Comp. Sci, 20, 6, 995, doi.org/10.1017/S0960129510000423 ; Mosca M. (2011), Handbook of Natural Computing. ; Childs A. (2010), Quantum algorithms for algebraic problems, Rev. Mod. Phys, 82, 1, 1, doi.org/10.1103/RevModPhys.82.1 ; Papadimitriou C. (1994), Computational Complexity. ; Cook S. (1973), Time-bounded random access machines, Proc. Forth Annual ACM Symposium on Theory of Computing, 1, 73. ; Shepherdson J. (1963), Computability of recursive functions, J. ACM, 10, 2, 217, doi.org/10.1145/321160.321170 ; Vollmer H. (1999), Introduction to Circuit Complexity, doi.org/10.1007/978-3-662-03927-4 ; Church A. (1936), An unsolvable problem of elementary number theory, American J. Mathematics, 58, 345, doi.org/10.2307/2371045 ; Abelson H. (1996), Structure and Interpretation of Computer Programs. ; Mitchell J. (2003), Concepts in Programming Languages. ; Deutsch D. (1985), Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. Lond, A 400, 97, doi.org/10.1098/rspa.1985.0070 ; Bohm C. (1964), On a family of Turing machines and the related programming language, ICC Bull, 3, 187. ; S. Aaronson and G. Kuperberg, "Complexity Zoo" <a target="_blank" href='http://qwiki.stanford.edu/index.php/Complexity_Zoo'>http://qwiki.stanford.edu/index.php/Complexity_Zoo</a> ; Yao A. (1993), Quantum circuit complexity, Proc. 34^th IEEE Symposium on Foundations of Computer Science, 1, 352. ; Nishimura H. (2002), Computational complexity of uniform quantum circuit families and quantum Turing machines, Theor. Comput. Sci, 276, 147, doi.org/10.1016/S0304-3975(01)00111-6 ; Vazirani U. (2002), A survey of quantum complexity theory, Proc. Sympos. Appl. Math, 1, 58. ; Garey M. (1979), Computers and Intractability: a Guide to the Theory of NP-Completeness. ; U. Zwick, "Scribe notes of the course Boolean circuit complexity" <a target="_blank" href='http://www.cs.tau.ac.il/~zwick/scribe-boolean.html'>http://www.cs.tau.ac.il/~zwick/scribe-boolean.html</a> ; Hirvensalo M. (2001), Quantum computing, doi.org/10.1007/978-3-662-04461-2 ; Deutsch D. (1989), Quantum computational networks, Proc. R. Soc. Lond, A 425, 73, doi.org/10.1098/rspa.1989.0099 ; Toffoli T. (1981), Bicontinuous extension of reversible combinatorial functions, Math. Syst. Theory, 14, 13, doi.org/10.1007/BF01752388 ; Nielsen M. (2000), Quantum Computation and Quantum Information. ; Barenco A. (1995), Elementary gates for quantum computation, Phys. Rev, A 52, 3457, doi.org/10.1103/PhysRevA.52.3457 ; Deutsch D. (1937), Universality in quantum computation, Proc. R. Soc. Lond, 1, 449. ; Shende V. (2004), Minimal universal two-qubit controlled-NOT-based circuits, Phys. Rev, A 69, 062321, doi.org/10.1103/PhysRevA.69.062321 ; Möttönen M. (2004), Quantum circuits for general multiqubit gates, Phys. Rev. Lett, 93, 13, 130502, doi.org/10.1103/PhysRevLett.93.130502 ; Vartiainen J. (2004), Efficient decomposition of quantum gates, Phys. Rev. Lett, 92, 177902, doi.org/10.1103/PhysRevLett.92.177902 ; Aaronson S. (2004), Improved simulation of stabilizer circuits, Phys. Rev, A 70, 5, 052328, doi.org/10.1103/PhysRevA.70.052328 ; Knill E. (1996), Conventions for quantum pseudocode, Tech. Rep. ; B. Ömer, "Structured quantum programming", <i>Ph.D. Thesis</i>, Vienna University of Technology, Vienna, 2003. ; Nagarajan R. (2007), Simulating and compiling code for the sequential quantum random access machine, Electronic Notes in Theoretical Computer Science, 170, 101, doi.org/10.1016/j.entcs.2006.12.014 ; Cleve R. (1996), Schumacher's quantum data compression as a quantum computation, Phys. Rev, A 54, 4, 2636, doi.org/10.1103/PhysRevA.54.2636 ; Cormen T. (2001), Introduction to Algorithms. ; Svore K. (2004), Toward a software architecture for quantum computing design tools, null, 1. ; Svore K. (2006), A layered software architecture for quantum computing design tools, Computer, 39, 1, 74, doi.org/10.1109/MC.2006.4 ; S. Bettelli, "Toward an architecture for quantum programming", <i>Ph.D. Thesis</i>, Università di Trento, Trente, 2002. ; Grover L. (1998), Quantum computers can search rapidly by using almost any transformation, Phys. Rev. Lett, 80, 4329, doi.org/10.1103/PhysRevLett.80.4329 ; M. Mosca, "Quantum computer algorithms", <i>Ph.D. Thesis</i>, Wolfson College, University of Oxford, Oxford, 1999. ; Bennett C. (1992), Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states, Phys. Rev. Lett, 69, 2881, doi.org/10.1103/PhysRevLett.69.2881 ; Brassard G. (2005), Quantum pseudotelepathy, Found. Phys, 35, 1877, doi.org/10.1007/s10701-005-7353-4 ; Bacon D. (2010), Recent progress in quantum algorithms, Commun. ACM, 53, 2, 84, doi.org/10.1145/1646353.1646375 ; Knill E. (2002), Encyclopedia of Mathematics, Supplement. ; Bettelli S. (2003), Toward an architecture for quantum programming, Eur. Phys. J, D 25, 2, 181. ; Mauerer W. (2005), Master's Thesis. ; H. Mlnařík, "Operational semantics and type soundness of quantum programming language LanQ", <i>Ph.D. Thesis</i>, Masaryk University, Brno, 2007. ; Mlnařík H. (2008), Semantics of quantum programming language LanQ, Int. J. Quant. Inf, 6, 1, Supp., 733, doi.org/10.1142/S0219749908004031 ; Gay S. (2006), Quantum programming languages: survey and bibliography, Math. Struct. Comput. Sci, 16, 4. ; Unruh D. (2006), Quantum programming languages, Informatik - forschung und entwicklung, 21, 1-2, 55, doi.org/10.1007/s00450-006-0012-y ; Rüdiger R. (2007), Quantum programming languages: an introductory overview, Comput. J, 50, 2, 134, doi.org/10.1093/comjnl/bxl057 ; Ömer B. (1998), Master's Thesis. ; B. Ömer, "Quantum programming in QCL", <i>Master's Thesis</i>, Vienna University of Technology, Vienna, 2000. ; H. Weimer, <i>The C Library for Quantum Computing and Quantum Simulation Version 1.1.0</i> <a target="_blank" href='http://www.libquantum.de/'>http://www.libquantum.de/</a> ; Miszczak J. (2005), Numerical simulations of mixed states quantum computation, Int. J. Quant. Inf, 3, 1, 195, doi.org/10.1142/S0219749905000748 ; Gawron P. (2010), Extending scientic computing system with structural quantum programming capabilities, Bull. Pol. Ac.: Tech, 58, 1, 77. ; Mlnařík H. (2006), LanQ - Operational semantics of quantum programming language LanQ. ; A. van Tonder (2004), A lambda calculus for quantum computation, SIAM J. Comput, 33, 5, 1109, doi.org/10.1137/S0097539703432165 ; Selinger P. (2004), Towards a quantum programming language, Math. Struct. Comput. Sci, 14, 4, 527, doi.org/10.1017/S0960129504004256 ; Kernighan B. (1988), C Programming Language. ; Deutsch D. (1992), Rapid solution of problems by quantum computation, Proc. Roy. Soc. Lond, A 439, 553, doi.org/10.1098/rspa.1992.0167 ; Wootters W. (1982), A single quantum cannot be cloned, Nature, 299, 802, doi.org/10.1038/299802a0 ; Vedral V. (1996), Quantum networks for elementary arithmetic operations, Phys. Rev, A 54, 147, doi.org/10.1103/PhysRevA.54.147 ; Selinger P. (2004), A brief survey of quantum programming languages, Proc. 7th Int. Symposium on Functional and Logic Programming 2998 of LNCS, 1, 1, doi.org/10.1007/978-3-540-24754-8_1 ; Hughes J. (1989), Why functional programming matters, Comput. J, 32, 2, 98, doi.org/10.1093/comjnl/32.2.98 ; A. Sabry, "Modeling quantum computing in Haskell", <i>ACM SIGPLAN Haskell Workshop</i> 1, CD-ROM (2002). ; Karczmarczuk J. (2003), Structure and interpretation of quantum mechanics: a functional framework, Proc. ACM SIGPLAN Workshop on Haskell, 1, 50, doi.org/10.1145/871895.871901 ; Hutton G. (2007), Programming in Haskell, doi.org/10.1017/CBO9780511813672