RUS  ENG
Full version
SEMINARS

Quantum computation
May 3, 2024 13:10, Steklov Mathematical Institute, Room 430 (8 Gubkina) + Zoom


Lecture 12. Unstructured search algorithm, quantum Fourier transform

V. I. Yashin


https://youtu.be/8qgCGEWv14s

Abstract: 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.


© Steklov Math. Inst. of RAS, 2024