
Квантовое преобразование Фурье — это метод, используемый в квантовых вычислениях для улучшения обнаружения сигналов, точности сенсоров и вычислительной эффективности.Квантовое преобразование Фурье — это унитарное отображение, которое переводит вычислительный базис |j⟩ в равномерную суперпозицию с фазами exp(2π i j k / N), где N = 2^n. Оно является квантовым аналогом дискретного преобразования Фурье и может быть реализовано с помощью O(n^2) гейтов, что даёт экспоненциальное ускорение относительно классического БПФ, требующего O(N log N) операций над N-элементным вектором. QFT лежит в основе алгоритмов поиска скрытой периодичности и оценки фазы.
Впервые описано в рамках алгоритма факторизации Питера Шора (1994). Эффективная конструкция с полиномиальным числом вентилей разработана Доном Копперсмитом (1994) и одновременно группой Дойча. Ранее, в 1985 году, Дэвид Дойч показал принципиальную возможность ускорения с помощью квантового параллелизма. С математической точки зрения QFT является реализацией преобразования Вигнера над конечным полем и тесно связано с теорией представлений групп.
Квантовая схема начинается с состояния |x_1 x_2 ... x_n⟩. Применяется H к первому кубиту, создавая суперпозицию (|0⟩ + e^{2π i 0.x_1}|1⟩). Затем подаётся управляемый R_2 от второго кубита, добавляя к фазе вклад exp(2π i 0.x_1 x_2), и так далее до R_n. Те же операции повторяются на втором кубите с поворотами R_2...R_{n-1}, и т.д. Итоговая амплитуда для состояния |k⟩ равна (1/√N) Σ_j exp(2π i j k / N) x_j, где x_j — входная амплитуда. При измерении на выходе распределение вероятностей сосредоточено вблизи частоты, кратной 1/T, если во входных данных была скрыта периодичность T.
Сердце алгоритма Шора, угрожающего современным системам шифрования RSA, а также ключевой этап оценки фазы в квантовых вычислениях — от поиска собственных чисел до оценки периодичности скрытых закономерностей.
Квантовое преобразование Фурье не может быть напрямую использовано для сжатия фото или видео, потому что результат остаётся внутри квантового чипа и разрушается при считывании; зато для выуживания глобальных периодичностей оно в тысячи раз экономит время.















