**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).

- Verify that four applications of the
**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.

- Quantum communication, quantum encryption (Gate)
- Type rules and orthogonality rules for QML (Will)
- Re-work monadic implementation of quantum computations using state and single-assignment (Michael)
- An object-oriented simulator of quantum computing (Roshan)
- Read and write a summary of Minds, Machines, and the Multiverse: The Quest for the Quantum Computer by Julian Brown (Beenish)
- Write a paper explaining the transactional interpretation of quantum mechanics (Craig)
- Implement Shor's algorithm in a generic way that can be instantiated to a classical or quantum computation. You should probably start by looking at the code provided by Matt. (Eric, Leon)
- Genetic algorithms and quantum computation. (Matt)
- Contrasting two approaches to quantum computing: topological vs. category-theoretical. (Jennifer)
- Implementing the multi-universe interpretation of quantum mechanics. (John)
- Complexity theory and quantum mechanics (Ramyaa)

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