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 xoring 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

• 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)