Lecture 10. Unstructured database search and Quantum Fourier Transform

We discussed Grover's algorithm for finding an element in unstructured database, which finds some element in $\mathcal{O}(\sqrt{N})$ oracle accesses, as opposed to the classical algorithm which requires $\mathcal{O}(N)$ accesses. In addition, we discuss how to realize the Fourier transform over cyclic groups $\mathbb{Z}_N$. For the case $N = 2^n$, we have written out a concrete $n$-qubit circuit, for arbitrary $N$ we can use the phase estimation algorithm.