phase
gate give the
identity. Use lincomp
from our Haskell library and print the
linear operator resulting from the compositions.
controlled qnot
in our code).
inverseC
.
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.
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 b1Please prove that your construction is indeed reversible.
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 |