Лекция 10. Поиск в неупорядоченной базе данных и квантовое преобразование Фурье.

Мы обсудили алгоритм Гровера для поиска в неупорядоченной базе данных, который позволяет найти некоторый элемент за $\mathcal{O}(\sqrt{N})$ обращений к оракулу, в отличие от классического алгоритма, который требует $\mathcal{O}(N)$ обращений. Кроме того, мы обсудили, как можно реализовывать преобразование Фурье над циклическими группами $\mathbb{Z}_N$. Для случая $N = 2^n$, мы выписали конкретную схему на $n$ кубитах, для произвольных $N$ можно пользоваться алгоритмом оценки фазы.