Квантовое преобразование Фурье
Аналог БПФ для квантового регистра — экспоненциально быстрее, хотя результат нельзя прочитать напрямую.
Если классическому быстрому преобразованию Фурье нужно порядка N log N операций, то квантовая версия обходится квадратом числа кубитов — то есть экспоненциально меньшим числом шагов относительно размера данных. Подвох в том, что преобразование оставляет амплитуды, которые нельзя осмотреть: можно лишь измерить, получив один-единственный исход.
Ценность проявляется, когда нужно узнать что-то о периодичности, а не об отдельных значениях. Именно этим пользуется алгоритм Шора: факторизация сводится к поиску периода функции, и здесь преобразование даёт ответ с высокой вероятностью за несколько запусков.