Week 6, summary 
---------------

1. Algorithms in the Oracle model
--------------------------------
 Grover's algorithm with provable quadratic improvement: 
 find an element in a database of N entries using \sqrt{N}$ queries. 


2. Lower bounds on Oracle model. 
 ------------------------------
I show the lower bound by BBBV, which shows that 
$\Omega(\sqrt(N))$ queries are required to solve the Grover 
problem, i.e. to distinguish between an oracle 
with one item for which $f(i)=1$ and an oracle with no such items.  

3. Density matrices and Ambainis's lower bound 
  --------------------------------------------
  I define the density matrix of a general quantum system. 
  I will then give Ambainis's lower bound on quantum speed up, 
  which is based on quantum intuition, 
  and shows that quadratic improvement is the best possible
  for grover's case. This lower bound uses density matrices.