A Programmer’s Survey of the Quantum Computing Paradigm

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.


Authors:



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).