Introduction to Probabilistic and Quantum Programming
BISS, Bertinoro
March 2014

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. The last part of the course is devoted to analyzing in some more detail the operational theory of probabilistic and quantum lambda calculi.

[1] P. Kaye, R. Laflamme, M. Mosca. An introduction to quantum computing. Oxford University Press, 2007.
[2] M. Hirvensalo. Quantum computing. Springer, 2004.
Teaching Material
Slides, Part I (3/5/2014) [ pdf ]
Slides, Part II (3/10/2014) [ pdf ]
Slides, Part III (3/10/2014) [ pdf ]
Research Papers (For more information on how to pass the exam, see here.)
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] Pablo Arrighi. Quantum computation explained to my mother. Technical Report, 2003.
[2] William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299(5886):802-803, 1982.
[3] 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.
[4] Grzegorz Rozenberg and Michael Main. Quantum pseudo-telepathy saves the world. EATCS Bulletin, (99), 2010.
[5] 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.