Part I.

1) Prove the three matrix identities in Slide 10
   http://vlsicad.eecs.umich.edu/Quantum/EECS598/lec/7a/Slide10.GIF

2) Consider the 2-input 2-output contolled-U gate, as on slide 12,
   http://vlsicad.eecs.umich.edu/Quantum/EECS598/lec/7a/Slide12.GIF
   with the 2x2 matrix U being

               (  1   1 )
    sqrt(2)i/2 (        )
               ( -1  1  )

   Decompose this gate into a circuit where all gates with more
   than one output are C-NOT gates. You need to achieve as small
   decomposition as possible.

3) Take the same matrix as in 2) and, with the same purpose,
   apply the QR-decomposition algorithm. Give an upper bound
   for the number of gates in the resulting circuit.
   

Part II.

  In the following problems, you are given classical reversible circuits
  consisting only of C-NOT gates.
  The 'o' represents the control bit, and the 'x' is the target bit.

1) Find a one-gate circuit that performs the same operation 
    as the following circuit.  
-x-o-x-o-o-x-o-
-o-x-o---x-o-x-
-------x-------


2) Using local reductions, reduce this circuit as much as possible:
-x-x---x-----o-----x-------
---o-o-o-x-o-x-o-o-o-x-o-x-
-o---x---o-x---x-x---o-x-o-


3) Find the smallest circuit that performs the same function as this:
---o---x-o-o-o---
-o---o-o-x---x-o-
-x-x-x-----x---x-