A Brief Introduction to Probabilistic and Quantum Programming
Universidade do Minho
May 2017
The course first introduces the basics of probabilistic and quantum algorithms, giving some hints about why these non-standard forms of computation are attracting the attention of theoretical computer science and programming language theory. We then move on and give a survey of recently introduced probabilistic and quantum programming languages, in the meantime trying to understand the issues these rather peculiar forms of programming raise.

Summary
Schedule
Teaching Material
Slides, Part I (5/5/2017) [ pdf ]
Slides, Part II (5/5/2017) [ pdf ]

References

Probabilistic Computing
[1] Karel De Leeuw, Edward F Moore, Claude E Shannon, and Norman Shapiro. Computability by probabilistic machines. Automata Studies, 34:183-198, 1956.
[2] Michael O Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963.
[3] Eugene S Santos. Probabilistic turing machines and computability. Proceedings of the American Mathematical Society, pages 704-710, 1969.
[4] Eugene S Santos. Computability by probabilistic turing machines. Transactions of the American Mathematical Society, 159:165-184, 1971.
[5] John Gill. Computational complexity of probabilistic turing machines. SIAM Journal on Computing, 6(4):675-695, 1977.
Quantum Computing
[1] P. Kaye, R. Laflamme, M. Mosca. An introduction to quantum computing. Oxford University Press, 2007.
[2] M. Hirvensalo. Quantum computing. Springer, 2004.
[2] Pablo Arrighi. Quantum computation explained to my mother. Technical Report, 2003.
[3] William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299(5886):802-803, 1982.
[4] Charles H Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K Wootters. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Physical Review Letters, 70(13):1895, 1993.
[5] Grzegorz Rozenberg and Michael Main. Quantum pseudo-telepathy saves the world. EATCS Bulletin, (99), 2010.
[6] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219. ACM, 1996.
Probabilistic Programming Languages
[1] Raymond Ng and Venkatramanan Siva Subrahmanian. Probabilistic logic programming. Information and Computation, 101(2):150-201, 1992.
[2] Noah Goodman, Vikash Mansinghka, Daniel Roy, Keith Bonawitz, and Daniel Tarlow. Church: a language for generative models. arXiv Preprint, 2012.
[3] Johannes Borgström, Andrew D Gordon, Michael Greenberg, James Margetson, and Jurgen Van Gael. Measure transformer semantics for bayesian machine learning. In Proceedings of the 20th European Symposium on Programming (ESOP), pages 77-96. Springer, 2011.
Quantum Programming Languages
[1] Bernhard Omer. Structured quantum programming. Information Systems, page 130, 2003.
[2] Jeff W Sanders and Paolo Zuliani. Quantum programming. In Mathematics of Program Construction, pages 80-99. Springer, 2000.
[3] Peter Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527-586, 2004.
[4] Thorsten Altenkirch and Jonathan Grattage. A functional quantum programming language. In Proceedings of the 20th Symposium on Logic in Computer Science (LICS), pages 249-258. IEEE, 2005.
[5] Alessandra Di Pierro and Herbert Wiklicky. Quantum constraint programming. Technical report, 2001.
[6] Stefano Bettelli, Tommaso Calarco, and Luciano Serafini. Toward an architecture for quantum programming. The European Physical Journal D-Atomic, Molecular, Optical and Plasma Physics, 25(2):181-200, 2003.
Lambda Calculus
[1] Gordon D. Plotkin. Call-by-name, call-by-value and the λ-calculus. Theoretical Computer Science, 1(2):125-159, 1975.
[2] Samson Abramsky. The lazy lambda calculus. Research topics in functional programming, pages 65-116, 1990.
[3] Andrew Pitts. Howe’s method for higher-order languages. In Advanced Topics in Bisimulation and Coinduction, volume 52 of Cambridge Tracts in Theoretical Computer Science, pages 197-232. 2011.
Probabilistic and Quantum Lambda Calculi
[1] Claire Jones and Gordon D Plotkin. A probabilistic powerdomain of evaluations. In Proceedings of the 4th Symposiun on Logic in Computer Science (LICS), pages 186-195. IEEE, 1989.
[2] Norman Ramsey and Avi Pfeffer. Stochastic lambda calculus and monads of probability distributions. ACM SIGPLAN Notices, 37(1):154-165, 2002.
[3] Ugo Dal Lago and Margherita Zorzi. Probabilistic operational semantics for the lambda calculus. RAIRO-Theoretical Informatics and Applications, 46(03):413-450, 2012.
[4] Ugo Dal Lago, Davide Sangiorgi, and Michele Alberti. On coinductive equivalences for higher-order probabilistic functional programs. In Proceedings of the 41st annual ACM Symposium on Principles of Programming Languages (POPL), pages 297-308. ACM, 2014.
[5] Peter Selinger and Benoit Valiron. A lambda calculus for quantum computation with classical control. Mathematical Structures in Computer Science, 16(3):527-552, 2006.
[6] Ugo Dal Lago, Andrea Masini, and Margherita Zorzi. On a measurement-free quantum lambda calculus with classical control. Mathematical Structures in Computer Science, 19(2):297-335, 2009.
[7] Ugo Dal Lago, Andrea Masini, and Margherita Zorzi. Quantum implicit computational complexity. Theoretical Computer Science, 411(2):377-409, 2010.