February 18, 2005
4:00 - 5:00, LH 102

Towards a High-Level Quantum Programming Language

Thorsten Altenkirch

Abstract:
Quantum programming tries to exploit the strange properties of quantum physics to run programs much faster than on any conventional hardware. A famous quantum algorithm is Shor's factorisation algorithm, which entails that on a quantum computer we can crack cryptosystems like RSA. While nobody has yet built quantum hardware of interesting size, we are already trying to understand how to program quantum computers. Most of these approaches are based on quantum circuits which can be modelled by unitary operators on finite-dimensional complex Hilbert spaces. On this level it seems quite hard to understand what your algorithm is actually doing, and it is also difficult to design new ones. Ongoing research as Nottingham (joint venture Mathematical Physics and Computer Science) attempts to overcome this by developing a functional quantum programming language (QML). The design of this language is inspired by comparing classical computation and quantum computation, identifying the similarities and differences. A draft paper on QML is available and a compiler is under development. We are collaborating with Amr Sabry and Juliana Vizotto (IU) on the constructive semantics and reasoning principles for QML. Joint work with Jonathan Grattage.

Biography:
Thorsten Altenkirch completed his PhD in 1993 at the University of Edinburgh, Scotland, working on constructive Type Theory and formal proof development. Subsequently, he worked as a researcher at Chalmers University in Gothenbug, Sweden, and at the University of Edinburgh. In 1996 he became lecturer at the University of Munich, Germany and since 2000 he is lecturer at the University of Nottingham, England. He is working in Type Theory, formal program development, constructive logic, category theory and quantum computing.