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

Квантовое преобразование Фурье (КПФ) — это квантовый алгоритм, реализующий дискретное преобразование Фурье над вектором амплитуд квантового состояния. Является ключевым компонентом многих квантовых алгоритмов, включая алгоритм Шора для факторизации целых чисел и алгоритм оценки квантовой фазы. КПФ представляет собой линейное унитарное преобразование, действующее на квантовый регистр из \(n\) кубитов, и выполняет преобразование Фурье над \(2^n\) комплексными амплитудами состояния.

Математическое определение

Пусть \(|j\rangle\) — базисное состояние квантового регистра из \(n\) кубитов, где \(j\) — целое число от 0 до \(N-1\), \(N = 2^n\). Квантовое преобразование Фурье отображает состояние \(|j\rangle\) в суперпозицию:

\[ \text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega_N^{jk} |k\rangle, \]

где \(\omega_N = e^{2\pi i / N}\) — примитивный корень \(N\)-й степени из единицы. В общем виде преобразование действует на произвольное состояние \(|\psi\rangle = \sum_{j=0}^{N-1} x_j |j\rangle\) как:

\[ \text{QFT}|\psi\rangle = \sum_{k=0}^{N-1} y_k |k\rangle, \quad y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega_N^{jk}. \]

Таким образом, КПФ является точным квантовым аналогом дискретного преобразования Фурье (ДПФ), но применяется не к классическим данным, а к амплитудам квантового состояния.

Отличие от классического преобразования Фурье

Классическое ДПФ над вектором из \(N\) чисел требует \(O(N \log N)\) операций с использованием быстрого преобразования Фурье (БПФ). Квантовое преобразование Фурье выполняется за \(O((\log N)^2) = O(n^2)\) квантовых вентилей, что экспоненциально быстрее классического аналога. Однако это ускорение достигается за счёт того, что КПФ не выдаёт все коэффициенты \(y_k\) в явном виде — результат существует в виде квантовой суперпозиции, и извлечение информации требует измерения, которое разрушает состояние. Поэтому КПФ эффективно используется в алгоритмах, где выходные данные обрабатываются квантово (например, в алгоритме Шора) или где требуется оценка фазы.

Схема реализации

Квантовое преобразование Фурье реализуется с помощью последовательности однокубитных и двухкубитных вентилей. Для регистра из \(n\) кубитов схема включает:

1. Вентили Адамара (\(H\)) — создают суперпозицию на каждом кубите.
2. Управляемые фазовые вентили (\(R_k\)) — вносят фазовые сдвиги между кубитами. Вентиль \(R_k\) определяется как:

\[ R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}. \]

1. Перестановка кубитов (SWAP-вентили) — в конце схемы порядок кубитов обращается, так как в стандартном определении КПФ младший кубит соответствует старшему разряду.

Стандартная схема для \(n\) кубитов использует \(O(n^2)\) вентилей: \(n\) вентилей Адамара, \(\frac{n(n-1)}{2}\) управляемых фазовых вентилей и \(O(n)\) SWAP-вентилей. Существуют оптимизированные варианты, требующие \(O(n \log n)\) вентилей, но они менее распространены.

Пример для 3 кубитов

Для \(n=3\) (\(N=8\)) КПФ преобразует состояние \(|j\rangle = |j_1 j_2 j_3\rangle\) (где \(j_1\) — старший бит) в:

\[ \text{QFT}|j_1 j_2 j_3\rangle = \frac{1}{\sqrt{8}} \left( |0\rangle + e^{2\pi i 0.j_3} |1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i 0.j_2 j_3} |1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i 0.j_1 j_2 j_3} |1\rangle \right), \]

где \(0.j_1 j_2 j_3\) — двоичная дробь. Схема состоит из трёх вентилей Адамара, трёх управляемых фазовых вентилей (с разными углами) и трёх SWAP-вентилей для обращения порядка.

Применение

Алгоритм Шора

Наиболее известное применение КПФ — в алгоритме Шора для факторизации целых чисел. Алгоритм сводит задачу факторизации к задаче нахождения периода функции, а КПФ используется для эффективного вычисления периода через оценку фазы. Без КПФ алгоритм Шора не имел бы экспоненциального ускорения.

Алгоритм оценки квантовой фазы

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

Квантовое преобразование Фурье в задачах обработки сигналов

Хотя прямое применение КПФ для классической обработки сигналов ограничено из-за необходимости измерения, существуют квантовые алгоритмы, использующие КПФ для анализа спектральных характеристик квантовых состояний. Например, в квантовой томографии и спектроскопии.

Квантовое машинное обучение

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

Обратное квантовое преобразование Фурье

Обратное КПФ (IQFT) определяется аналогично, но с заменой \(\omega_N^{jk}\) на \(\omega_N^{-jk}\). IQFT применяется, например, в алгоритме оценки фазы для получения результата. Схема IQFT строится обращением схемы прямого КПФ: порядок вентилей меняется на противоположный, а фазовые вентили заменяются на сопряжённые.

Сложность и ресурсы

КПФ требует \(O(n^2)\) однокубитных и двухкубитных вентилей. Для \(n=100\) кубитов это около 10 000 вентилей, что делает алгоритм практичным для современных квантовых компьютеров с низким уровнем шума. Однако на реальных устройствах с ошибками вентилей глубина схемы может быть критичной, и используются методы оптимизации, такие как сокращение числа SWAP-вентилей или использование приближённого КПФ.

Приближённое квантовое преобразование Фурье

В некоторых задачах можно использовать приближённое КПФ, которое отбрасывает вентили с малыми фазовыми сдвигами (например, \(R_k\) для \(k > \log n\)). Это снижает сложность до \(O(n \log n)\) и уменьшает накопление ошибок, но вносит погрешность в результат. Приближённое КПФ применяется в алгоритмах, где точность не критична, например, в некоторых квантовых симуляциях.

Реализация на квантовых компьютерах

КПФ реализовано на многих квантовых платформах, включая сверхпроводниковые кубиты (IBM, Google), ионные ловушки (IonQ, Honeywell) и фотонные системы. Например, в 2019 году Google продемонстрировал КПФ на 53-кубитном процессоре Sycamore в рамках задачи квантового превосходства. Однако из-за шума и декогеренции точное выполнение КПФ на больших \(n\) остаётся сложной задачей.

Ограничения

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

Источники

• Nielsen M. A., Chuang I. L. Quantum Computation and Quantum Information: 10th Anniversary Edition. — Cambridge University Press, 2010.
• Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM Journal on Computing. — 1997. — Vol. 26, No. 5.
• Cleve R., Ekert A., Macchiavello C., Mosca M. Quantum algorithms revisited // Proceedings of the Royal Society of London. Series A. — 1998. — Vol. 454, No. 1969.
• Прескилл Дж. Квантовая информация и квантовые вычисления. — М.: Регулярная и хаотическая динамика, 2011.