Лекция 12. Алгоритм поиска в неупорядоченной базе данных, преобразование Фурье

На этой Лекции мы поговорили об алгоритме Гровера и о реализации преобразования Фурье квантовыми схемами. Алгоритм Гровера позволяет решить проблему нахождения элемента в неупорядоченной базе данных. Решение этой проблемы с использованием возможностей квантовой механики даёт квадратичное преимущество относительно классического решения этой задачи. При помощи элементов вида $C\mathrm{NOT}+U(2)$ можно реализовать преобразование Фурье над абелевой группой $\mathbb{Z}_{2^n}$. При помощи такого преобразования Фурье можно приближённо решать задачу оценки фазы, возникаемой при действии унитарного преобразования на собственный вектор. Благодаря алгоритму оценки фазы получается реализовать преобразование Фурье над произвольной конечно абелевой группой.