The Quantum IO monad is a purely functional interface to quantum programming implemented as a Haskell library. At the same time it provides a constructive semantics of quantum programming. The QIO monad separates reversible (i.e. unitary) and irreversible (i.e. probabilistic) computations and provides a reversible let operation (ulet), allowing us to use ancillas (auxiliary qubits) in a modular fashion. QIO programs can be simulated either by calculating a probability distribution or by embedding it into the IO monad using the random number generator. As an example we present a complete implementation of Shor's algorithm. We present an interface from a pure functional programming language, Haskell, to quantum programming: the Quantum IO monad, and use it to implement Shor's factorisation algorithm. The implementation of the QIO monad provides a constructive semantics for quantum programming, i.e. a functional program which can also be understood as a mathematical model of quantum computing. Actually, the Haskell QIO library is only a first approximation of such a semantics, we would like to move to a more expressive language which is also logically sound. Here we are thinking of a language like Agda (Norell (2007)), which is based on Martin Löf's Type Theory. We have already investigated this approach of functional specifications of effects in a classical context (Swierstra and Altenkirch (2007, 2008); Swierstra (2008) ). At the same 1 2 Thorsten Altenkirch and Alexander S. Green time the QIO monad provides a high level interface to a hypothetical quantum computer. To make the presentation accessible to the non-Haskell programmer, we shall give a brief introduction to the language in section 1.2. The QIO monad separates reversible (i.e. unitary) and irreversible (i.e. probabilistic) computations and provides a reversible let operation (ulet), allowing us to use ancillas (auxiliary qubits) in a modular fashion. QIO programs can be simulated either by calculating a probability distribution or by embedding it into the IO monad using the random number generator. An overview of the Quantum IO Monad (QIO) is given in section 1.3. Exploiting Haskell's class system we can present our algorithms in a high level way, implementing abstractions using functional programming technology. We describe the implementation of Shor's algorithm in some detail (section 1.5) also covering the necessary reversible arithmetic (section 1.4). The actual implementation of QIO is covered in section 1.6, where we focus in detail on the design of the QIO quantum simulator functions sim and run. Quantum programming is able to exploit the strange nature of quantum physics to achieve classically impossible, or rather infeasible, tasks. Most famously Shor's algorithm shows that on a quantum computer we can factor a number in polynomial time, hence we could break many encryption schemes. While physicists are working on building working quantum circuits with more than a handful of qubits, we computer scientists grapple with the challenges quantum computing creates for software: in designing algorithms, like Shor's which exploit quantumness; but also in designing languages which support abstractions relevant for quantum computing. See Gay (2006) and Rüdiger (2007) for recent language surveys. Here we investigate a different approach: instead of implementing a new language from scratch we provide a monadic interface to do quantum programming in Haskell -the quantum IO monad (QIO). This has a number of advantages: • we can exploit existing means of abstraction present in Haskell to structure our quantum programs, indeed we will give an example of this by implementing the class Qdata which relates classical data-types with their quantum counterparts; • We can explore which semantic primitives are most useful to structure quantum programs, without committing to a particular view too early; The Quantum IO Monad • we can exploit the existing support for Haskell, in the form of tools and libraries to develop our quantum programs. We believe that a purely functional approach is ideally suited for this venture, since it already makes effects explicit (in Haskell via the IO monad) and is close to a mathematical semantics of quantum programming (see our introductory comments on constructive semantics). While QIO realises the infrastructure we need to control a quantum computer from Haskell, we don't have to wait until the physicists develop a practical quantum computer, we can use the same interface to run a quantum simulator. Our approach is inspired by the first author's work with Wouter Swierstra on functional specifications of IO (Swierstra and Altenkirch (2007)). Indeed, we provide some choice here: we can embed QIO into the IO monad using pseudo-random numbers to simulate quantum randomness, we can statically calculate the probability distribution of possible results given a quantum program and we can simulate the classical subset of our quantum operations directly. The latter is useful for testing components efficiently since the quantum simulation generates a considerable overhead. All the code described in this chapter, i.e. the implementation of QIO and the quantum algorithms implemented in it are available from the second author's web-page (Green (2008)). There are a number of papers on modelling quantum programming in Haskell, (Mu and Bird (2001); Sabry (2003) ; Karczmarczuk (2003) ; Vizzotto et al. (2006) ). They describe different abstractions one can use to simulate quantum computation in a functional setting -however, our approach is different in that we provide a high level interface in the spirit of the IO monad which provides an interface to a hypothetical quantum computer. Our previous work on QML (Altenkirch and Grattage (2005) ) proposed a first order functional quantum programming language, the present work is more modest but gives us a stepping stone to experiment with various alternative structures useful for structuring quantum programming and also to implement future versions of languages like QML.
The Quantum IO Monad REF is embedded in Haskell and offers consistent operational semantics.
1 The Quantum IO Monad
Computer Science