Week 4, summary
---------------

1. Quantum Fast Fourier Transform (QFFT) 
   ---------------------------
   Definition of Fourier transform over Z_N  
   reviewed of the classical fast Fourier transform circuit
   a recursive construction of a quantum circuit for FFT. 
   (This can be taken from Vazirani's third lecture notes. 
    the quantum circuit presented there is not completely correct- 
    and some reordering of basis states should be added at the end. 
    I will point to this next lecture. )


2   Shor's algorithm. 
    -----------------
    I will present Shor's celebrated algorithm for factoring, 
    a problem which is thought to be hard for classical computers.     
    I will start with Classical reduction from factoring to order finding, 
    using number theory. 
    I will present the order finding algorithm: 
    given $a$, $N$ coprime, find the order of $a$ mod $N$. 
    (r is the order of a mod N if $a^r=1( mod N)$ 
    and r is the minimal integer for which this is true.)
    The algorithm uses Fourier transforms over $Z_Q$, where $Q$ 
    is much larger than $N$. The algorithm is polynomial in 
    log(N).  
    I will first analyze the exact case, which is when r 
    divides Q exactly. (this is a toy model- this case is easy 
    even for classical computers.)

3.  Shor's algorithm, the general case.
    ----------------------------------- 
    The second lecture will be devoted to the analysis of 
    the general case. 
    I will show how using continued fractions one can overcome 
    the problems arising there.