A Programmer’s Survey of the Quantum Computing Paradigm

Authors: Philippe Jorrand

Abstract:

Research in quantum computation is looking for the consequences of having information encoding, processing and communication exploit the laws of quantum physics, i.e. the laws which govern the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. This paper starts with a short survey of the principles which underlie quantum computing, and of some of the major breakthroughs brought by the first ten to fifteen years of research in this domain; quantum algorithms and quantum teleportation are very biefly presented. The next sections are devoted to one among the many directions of current research in the quantum computation paradigm, namely quantum programming languages and their semantics. A few other hot topics and open problems in quantum information processing and communication are mentionned in few words in the concluding remarks, the most difficult of them being the physical implementation of a quantum computer. The interested reader will find a list of useful references at the end of the paper.

Keywords: Quantum information processing, quantum algorithms, quantum programming languages.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331417

References:

[1] Abramsky, S., Coecke, B.: Physical traces: Quantum vs. Classical Information Processing. In: Blute, R., Selinger, P. (eds.): Category Therory and Computer Science (CTCS-02). Electronic Notes in Theoretical Computer Science 69, Elsevier (2003).
[2] Abramsky, S., Coecke, B.: A Categorical Semantics of Quantum Protocols. In: Ganzinger, H. (ed.): Logic in Computer Science (LICS 2004). IEEE Proceedings 415-425 (2004).
[3] Bennet, C., Brassard, G., Crepeau, C., Jozsa, R., Peres, A., Wootters: Teleporting an Unknown Quantum State via Dual Classical and EPR Channels. Physical Review Letters, 70:1895-1899 (1993).
[4] Birkhoff, G., von Neumann, J.: Annals of Mathematics 37, 823 (1936).
[5] Brunet, O., Jorrand, P.: Dynamic Logic for Quantum Programs. International Journal of Quantum Information (IJQI). World Scientific, 2(1):45-54 (2004).
[6] Carloza, D., Cuartero, F., Valero, V., Pelayo, F.L., Pardo, J.: Algebraic Theory of Probabilistic and Nondeterministic Processes. The Journal of Logic and Algebraic Programming 55(1-2):57-103 (2003).
[7] D-Hondt, E., Panangaden, P.:Quantum Weakest Preconditions. In (25).
[8] Deutsch, D.: Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. In: Proceedings Royal Society London A, 400:97 (1985).
[9] Durr, C., Heiligman, M., Hoyer, P., Mhalla, M.: Quantum Query Complexity of some Graph Problems. In: Diaz, J. (ed): International Colloquium on Automata, Languages and Programming (ICALP-04), Lecture Notes in Computer Science, Vol. 3142, Springer-Verlag, 481- 493 (2004).
[10] Feynmann, R.P.: Simulating Physics with Computers. International Journal of Theoretical Physics 21:467 (1982).
[11] Gay, S.J., Nagarajan, R.: Communicating Quantum Processes. In (25).
[12] Girard, J.Y.: Between Logic and Quantic: a Tract. Unpublished manuscript (2004).
[13] Grover, L.K.: A Fast Quantum Mechanical Algorithm for Database Search. In: Proceedings 28th ACM Symposium on Theory of Computing (STOC-96) 212-219 (1996).
[14] Jorrand, P., Perdrix, S.: Unifying Quantum Computation with Projective Measurements only and One-Way Quantum Computation. Los Alamos e-print arXiv, http://arxiv.org/abs/quant-ph/0404125 (2004).
[15] Kempe, J.: Quantum Random Walks - An Introductory Overview. Los Alamos e-print arXiv, http://arxiv.org/abs/quant-ph/0303081 (2003).
[16] Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. American Mathematical Society, Graduate Studies in Mathematics, 47 (2002).
[17] Lalire, M., Jorrand, P.: A Process Algebraic Approach to Concurrent and Distributed Quantum Computation: Operational Semantics. In (25).
[18] Leung, D.W.: Quantum Computation by Measurements. Los Alamos eprint arXiv, http://arxiv.org/abs/quant-ph/0310189 (2003).
[19] Lomont, C.: The Hidden Subgroup Problem - Review and Open Problems. Los Alamos e-print arXiv, http://arxiv.org/abs/quantph/ 0411037 (2004).
[20] Milner, R.: Communication and Concurrency. Prentice-Hall (1999).
[21] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000).
[22] Ömer, B.: Quantum Programming in QCL. Master-s Thesis, Institute of Information Systems, Technical University of Vienna (2000).
[23] Raussendorf, R., Browne, D.E., Briegel, H.J.: Measurement-based Quantum Computation with Cluster States. Los Alamos e-print arXiv, http://arxiv.org/abs/quant-ph/0301052 (2003).
[24] Rieffel, E.G., Polak, W.: An Introduction to Quantum Computing for Non-Physicists. Los Alamos e-print arXiv, http://arxiv.org/abs/quantph/ 9809016 (1998).
[25] Selinger, P. (ed.): Proceedings of 2nd International Workshop on QuantumProgramming Languages http://quasar.mathstat.uottawa.ca/~selinger/qpl2004/proceedings.html (2004).
[26] Selinger, P.: Towards a Quantum Programming Language. Mathematical Structures in Computer Science. Cambridge University Press, 14(4):525- 586 (2004).
[27] Shor, P.W.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Proceedings (1994).
[28] Van Tonder, A.: A Lambda Calculus for Quantum Computation. Los Alamos e-print arXiv, http://arxiv.org/abs/quant-ph/0307150 (2003).
[29] Van Tonder, A.: Quantum Computation, Categorical Semantics and Linear Logic. Los Alamos e-print arXiv, http://arxiv.org/abs/quantph/ 0312174 (2003).
[30] Zuliani, P.: Quantum Programming. PhD Thesis, St. Cross College, Oxford University (2001).
[31] Advanced Research and Development Activity (ARDA): A Quantum Information Science and Technology Roadmap, http://qist.lanl.gov, (2004).