Lecture 12. Unstructured search algorithm, quantum Fourier transform

In this Lecture, we talked about Grover's algorithm and implementation of Fourier transform with quantum circuits. Grover's algorithm allows to solve the problem of finding an element in an unstructured database. The solution of this problem using the quantum mechanics gives a quadratic advantage in comparison with the classical solution of this problem. By using elements of the form $C\mathrm{NOT}+U(2)$, one can realise a Fourier transform over the abelian group $\mathbb{Z}_{2^n}$. Using such a Fourier transform, one can approximate the problem of estimating the phase resulting from the action of a unitary transform on an eigenvector. Thanks to the phase estimation algorithm, it is possible to realise the Fourier transform over an arbitrary finitely abelian group.