5.4. Квантовое преобразование Фурье.

Пусть имеется система из кубитов. Ее состояние представляет собой вектор в гильбертовом пространстве размерности . Базисные состояния квантовой системы есть , где

Квантовое преобразование Фурье задается следующим унитарным преобразованием базисных состояний:

Преобразование Фурье базисных функций определяет соответствующее преобразование вектора состояния

Здесь

Последняя формула представляет собой преобразование Фурье комплексных амплитуд вероятности. Результат в точности соответствует так называемому классическому дискретному преобразованию Фурье, примененному к столбцу комплексных чисел , где (см. например [70]).

Обратное преобразование Фурье для амплитуд вероятности есть

Квантовое преобразование Фурье принципиально отличается от аналогичного дискретного преобразования Фурье классического сигнала (несмотря на тождество соответствующих формул). Дело в том, что в квантовой информатике мы имеем дело со специфическим «сигналом», который образован амплитудами вероятности (а не электрическими или механическими напряжениями как в классическом случае). В отличии от классического сигнала, квантовый «сигнал» нельзя измерить никаким «осциллографом» (при измерении квантовое состояние редуцируется в одно из базисных состояний). В то же время, в квантовой информатике мы можем оперировать векторами данных экспоненциально большой размерности (например при ).

Для простоты изложения остановимся более подробно на трехкубитовом преобразовании Фурье ( , ).

Например, базисное состояние будет претерпевать следующее изменение

Квантовое преобразование Фурье может быть построено на основе элементов Адамара и контролируемого преобразования фазы.

Пусть - следующее однокубитовое преобразование фазы:

На рисунке 5.6 изображен двухкубитовый элемент, осуществляющий контролируемое фазовое преобразование. Управляемый кубит (нижний) подвергается преобразованию , если управляющий кубит (верхний) находится в состоянии

Рис. 5.6 Двухкубитовый элемент, осуществляющий управляемое фазовое преобразование.

На рисунке 5.7 представлена квантовая цепь, обеспечивающая трехкубитовое преобразование Фурье

Рис. 5.7 Квантовая цепь для трехкубитового преобразования Фурье

Задача 5.13 Пусть на вход трехкубитовой квантовой схемы, изображенной на представленном выше рисунке, подается состояние . Покажите, что на выходе квантовой схемы будет состояние:

Решите ту же задачу для других входных состояний .

Решение задачи свидетельствует о том, что квантовая схема на рисунке действительно дает трехкубитовое преобразование Фурье с одной существенной оговоркой. Легко видеть, что для того, чтобы результат был правильный, на выходе схемы порядок следования кубитов должен быть обращен. Другими словами, двоичное представление состояний на выходе следует читать не слева направо, а справа налево: например означает состояние и т.д.

Конечно, на выходе схемы можно ввести дополнительные операции обмена состояниями кубитов, но с практической точки зрения это нецелесообразно (лучше договориться об инверсии порядка нумерации кубитов).

Представленная выше трехкубитовая схема допускает простое обобщение на произвольное число кубитов.

Общий алгоритм квантового преобразования Фурье может быть реализован с помощью схемы, изображенной на рисунке.

Рис. 5.8 Квантовая цепь для - кубитового преобразования Фурье

Подсчитаем число операций, необходимых для осуществления квантового преобразования Фурье. Из схемы видно, что с первым (верхним) кубитом можно связать преобразований (преобразование Адамара и фазовое преобразование), аналогично со вторым (сверху) кубитом можно связать преобразование и т.д. Полное число преобразований, равное сумме арифметической прогрессии, есть . Таким образом, число операций, необходимых для осуществления квантового преобразования Фурье, есть величина порядка . Отметим, что самые быстрые классические алгоритмы выполняют преобразование Фурье за порядка операций (так называемое быстрое преобразование Фурье). Таким образом, квантовый алгоритм имеет экспоненциальное преимущество по сравнению со своим классическим аналогом.

Пример. Пусть имеется 1000- кубитовое состояние ( ). Ему отвечает вектор состояния, описывающийся комплексными числами. Для осуществления классического быстрого преобразования потребуется проделать порядка операций. В то же время, квантовое преобразование над рассматриваемым вектором осуществляется примерно за операций.

Таким образом, экспоненциальное преимущество квантового алгоритма по сравнению с классическим позволит на квантовом компьютере ставить и решать задачи, которые никогда не будут решены на классическом компьютере.