## Assignments

• A1 (Due Thursday 22 Sep) Read the survey paper by Simon Gay accessible from his Bibliography on Quantum Programming Languages. Impelement our Toffoli circuit discussed in class using one of the programming languages described in the paper. (If the language has an accessible implementation then please produce an executable program to simulate the circuit; otherwise it is sufficient to describe the circuit abstractly.)

• A2 (Due Tuesday 4 Oct) The paper Basic concepts in quantum computation has a nice introduction to quantum circuits. The following exercises refer to this paper and the Haskell primitives discussed in class:
• Verify that four applications of the `phase` gate give the identity. Use `lincomp` from our Haskell library and print the linear operator resulting from the compositions.
• Repeat the above to verify the claim made on page 7 that four applications of the controlled phase operator produce the idendity.
• Implement the first circuit on page 7 and check that it does indeed correspond to cnot (or `controlled qnot` in our code).
• Implement the quantum adder on page 8. Test the adder with various input vectors (including vectors representing superpositions).

• A3 (Due Thursday 13 Oct) Here is a slightly improved version of the code for reversible circuits. It is missing a definition for calculting the inverse of the function denoted by a circuit (classical or quantum). Complete the definition of this function `inverseC`.

• A4 (Due Thursday 20 Oct) We have seen how to convert an arbitrary functions on booleans to a reversible function. The idea is captured in the following Haskell definition:
```torev :: (a -> Bool) -> ((a, Bool) -> (a, Bool))
torev f (xs,x) = (xs, x `xor` f xs)
```
We are given a function from a type `a` (representing any collection of booleans) to a single boolean result. We return a function which takes one additional input and produces all the original inputs as (garbage) outputs. The real output of the reversible function is calculating by applying the original (irreversible) function to its original inputs and `xor`ing the result with the new input. For example, a reversible `and` can be produced by writing `torev (uncurry (&&))`.

This construction does not immediately work if the original function returns anything other than a single boolean. For example, it is often natural to write functions that return more than one boolean:

```halfAdd :: (Bool,Bool) -> (Bool,Bool)
halfAdd (a,b) = let carryOut = a && b
sum = a `xor` b
in (carryOut,sum)
```
Try to generalize the construction to such cases. Extra credit for solutions written in Haskell.

• A5 (Due Thursday 3 Nov) We have seen how to convert an arbitrary function from `a -> b` to a reversible function (provided the type `b` supports an operation like `xor`). See Michael's solution for A4 for details. In this assignment, I would like to generalize this further to functions of type `a -> m b` where the type constructor `m` stands for either `Classical` or `Quantum` as previously discussed in the implementation of reversible circuits. Please turn in the Haskell code to construct such a reversible function and test it on several examples. Your examples should include classical and quantum variants of functions which take more inputs than outputs (something like the boolean `and`) and functions which produce more outputs than inputs (something like the function `delta x = vreturn (x,x)`). Consider also a function like:
```irr_k :: (Kleisli m, Monoidal m) => (Bool,Bool) -> m Bool
irr_k (b1,b2) = vreturn b1
```
Please prove that your construction is indeed reversible.

• A6 (Due any time) Fix the problems in A5 and find the best construction for the definition of orthogonality used in Cat.hs.

## Project Ideas

Everyone taking the class for credit is expected to individually complete one of these projects before the end of the term. (Projects do not have to be programming projects; they could involve writing a paper; doing some proofs; etc.)

## Presentations

 Date Topic Presenter 29 Sep. Background on linear algebra; Hilbert spaces Jennifer 4 Oct. Quantum Circuits in Ruby Roshan 11 Oct. Introduction to category theory Eric 18 Oct. Monads and arrows Michael 20 Oct. The quantum Turing machine Will 25 Oct. Shor's algorithm Matt 15 Nov. Reversibility and thermodynamics Craig 17 Nov. Grover's algorithm Beenish 29 Nov. Circuit simulation with measurements John 1 Dec. Quantum computing: topology vs. category theory Jennifer 1 Dec. Quantum communication and cryptography (I) Gate 6 Dec. Quantum communication and cryptography (II) Gate 6 Dec. Reversibility and thermodynamics Ramyaa (I) 8 Dec. Reversibility and thermodynamics Ramyaa (II) 8 Dec. Density matrics and superoperators Leon

sabry ... cs indiana edu