QML

Haskell provides Monadic programming constructs to enable computations that may involve side effects, one of the main Monads provided in Haskell is the IO Monad, which contains all the various IO functions that can be used in a Haskell program. Monads are used to contain impure functions that can produce side effects, and rap them so as to create pure functions whose results may include a description of any side-effects that occurred. These Monadic bindings enable any side effects that may occur to propagate through the program until they can be sensibly dealt with. A monad in Haskell is defined as a type constructor, along with a function, and a bind function denoted . The return function is used to put values of any datatype into the monad, and the bind function is used to apply functions of datatypes outside the monad to the value of that datatype contained within the monad. The result of the function being bound must be in the monad.

The type constructor for the QIO monad is:

the return function can simply be defined as the QReturn constructor, and the bind function needs to be given for each constructor as follows:

The type constructors of the QIO monad describe the operations that can be performed on a sort of `Quantum Register'’. relates to making qubits available for the computation, relates to the application of an actual quantum computation, and is used to apply a unitary operation to the relevant qubits that have been initialised. We’ll see shortly the definition of a unitary operation. The last constructor, relates to the final measurement of the Qbits after the computation has taken place.

So, we’ve seen that a quantum computation is defined as a unitary operation, which are defined in the monoid of unitary operations, denoted . A monoid in Haskell is again defined as a type constructor, with one of the constructors being denoted as the identity element, or . The binary operation of the monoid is denoted |mappend| and the definition must be given. In the case of the monoid, the type constructors and the corresponding
operations are defined by:

The type constructors of U represent the various operations that are required such that any unitary operation can be constructed, they correspond very closely to the operations described early for Quantum Computations. The constructor is for any single qubit rotation, and the actual rotation to be performed is the given which we’ll look at more closely later. The constructor is used to swap the position of the 2 given qubits. Finally the constructor is for conditionals, and the looks at the relevant qubit to decide whether or not the given unitary is run. The operation is used to build up bigger unitary operations from smaller ones.

All single qubit rotations can be defined as a unitary 2 by 2 matrix, and so a rotation as used in the U monoid can be defined as 4 complex numbers that represent the entries in the corresponding unitary matrix. Some common single qubit rotations can be given as examples, including the X rotation, which corresponds to the classical Not, and the Hadamard rotation which is used to take any qubit from it’s base state into an equal superposition of both base states.

because all rotations must be unitary, it is possible to create their inverses using the conjugate transpose as follows:

It is possible to create their inverses too:

It’s possible now to build up quantum computations, but the aim of the QIO monad is to enable these computations to be simulated. This is achieved through lifting the U monoid into another monoid named Unitary. Quantum computations that have been constructed in the U monoid must be lifted into “Pure'’ computations in the Unitary monoid, where qubits are assigned to the computations such that the computations can be run, thus changing the state of the qubits. The way a computation is then actually simulated by a user is by the use of a PMonad, which is a monad along with a function that describes how to display the state of the qubits.

The IO Monad can be extended into a PMonad by adding a function that uses the random number generator of the IO Monad to probabilistically give each of the qubits a true or false value.

Another PMonad can be defined such that the two probabilities are given as part of the result instead of being used to “collapse'’ the qubit amplitudes, as in the example above.

Then the eval function only needs to be coded once, but takes the PMonad as one of it’s arguments.

With the QIO Monad it’s now possible to create quantum computations and evaluate them. Some example QIO programs are given below:

The above program would create a random bit, by creating a qubit, applying the Hadamard rotation, and then measuring the qubit. Another example is a small program that creates a 2 qubit bell state. It proceeds by creating a qubit, applying the Hadamard to it, then making another qubit which is entangled with the first qubit using a conditional Not rotation. The 2 qubits are measured, and a pair of the two measurements is returned. The bell state means that the qubits are entangled such that they will always collapse to the same state as
one another.

Now that we have created the QIO Monad, we would like to come up with larger examples, including implementations of Shor’s and Grover’s algorithms. It should also be possible to use larger quantum data structures than individual qubits, creating them in the same way that classical data structures are defined from classical bits. It should again be possible to construct QIO programs from QML programs, and thus use the evaluation functions to simulate the running of QML programs.

This entry was posted on Friday, February 23rd, 2007 at 2:58 pm and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.