3 кубита
Квантовое преобразование Фурье
Квантовый аналог БПФ — сердце алгоритмов Шора и оценки фазы.
История
Разработано Коппенсмитом и Чуангом; используется с 1994 года.
Задача
Вычислить дискретное преобразование Фурье над амплитудами.
Математика
Продукт вентилей H и контролируемых фазовых сдвигов.
Сложность
O(n²) вентилей vs O(n·2^n) классически
vs Классика
Экспоненциальное ускорение для полного БПФ.