Nonstandard Programming

In recent years advances in program design have been achieved by extensions to the concept of computation. Quantum computations, probabilistic programs and (demonically) nondeterministic algorithms have achieved greater efficiency or simplicity (perhaps both) than can be matched by any standard computation. Shor's quantum algorithm for integer factorisation is exponentially more efficient (in size of input) than any known standard algorithm; Rabin's probabilistic algorithm for choice coordination amongst distributed agents has roughly constant expected execution time, compared with the optimal standard efficiency which is asymptotically proportional to the square root of the number of agents; and (demonic) nondeterminism provides a controlled way of abstracting, and hence simplifying, the description of any algorithm.

In this course we study all three programming paradigms and relate them to the standard model of computation. We begin by identifying the notion of programming structure and surveying the concept of Galois connection (aka adjunction) for relating such structures. Galois connections are used to relate the recursion-theoretic, relational and predicate-transformer models of standard programs. Probabilistic programs are introduced and related to standard programs. Quantum programs are introduced as a contemporary way of describing quantum computations, and modelled as probabilistic programs of a particular kind. In this form the usual quantum algorithms are studied and shown to meet their probabilistic or nondeterministic specifications.

By the end of the course participants are expected to appreciate the quantum model of computation, how to formalise it and how to relate it to the standard model and, more generally, to appreciate what constitutes a (perhaps nonstandard) paradigm of computation and the tools for studying it.

Prerequisite for the course is a sound knowledge of (standard!) procedural programming. After covering core material the choice from a wide range of topics (further theory of Galois connections, further probabilistic algorithms, quantum cryptography, quantum complexity, concurrent algorithms, quantum automata) will be determined by audience interest.

References (the first and last two will be handed out):

• Programs and Abstraction, course lecture notes by A.K.McIver, C.C.Morgan and J.W.Sanders.
• Quantum Computation and Quantum Information, M.A.Nielsen and I.L.Chuang, Cambridge University Press, 2000.
• Quantum Computing, J.Gruska, McGraw-Hill International (UK), (Advanced Topics in Computer Science), 1999.
• Quantum programming, J.W.Sanders and P.Zuliani, Mathematics of Program Construction, Springer-Verlag LNCS 1837, 80-99, 2000.
• Reasoning about probabilistic systems, A.K.McIver, C.C.Morgan and J.W.Sanders, to appear.