Week 3, summary
---------------

1. Basic quantum complexity. 
   ------------------------

   Definition of BPP, BQP, discussion about the uniform circuit 
   model. Reversible computation, proof that classical 
   computation can be done reversibly (P=revP), that 
   reversible classical computation is a subset of quantum computation, 
   proof that BPP is contained in BQP. 
   Clean reversible computation. 

2. Simple quantum algorithms. 
   -------------------------
   Quantum computation in the oracle model. 
   Deutsch Josza algorithm.
   Viewing vectors as functions.  
   Hadamard Fourier Transform, the Fourier basis vectors (characters.)  
   
3. Bernstein Vazirani's algorithm (just a remark- no details)
   Simon's algorithm. 
   Discussion about interference and entanglement, 
   and the relation to clean reversible computation. 

References: For the algorithms, look at my review, 
except for Bernstein Vazirani algorithm. (for this, look at 
Vazirani's home page, paper with Bernstein.)  
For Fourier transforms best is to wait for notes, and for 
the class in which I will discuss them in a more general way.  
I can't think of a good place that will give only the necessary 
stuff and not much more.   
For reversible computation- look at Preskill's notes, chapter 
6.1.3 (quantum computation part.)