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

Алгоритм Шора взламывает RSA. Алгоритм Гровера ускоряет поиск. HHL решает системы уравнений. Все три основаны на одном примитиве - Quantum Fourier Transform. Понять QFT значит понять механизм большинства квантовых алгоритмов с экспоненциальным ускорением.

• **IBM Quantum (2023)**: эксперименты с Kyber post-quantum cryptography проверяют устойчивость к QFT-based атакам; команда IBM опубликовала первую реализацию Kyber на квантовом процессоре.
• **Google + Caltech (2020)**: квантовая симуляция химических реакций через QPE на 12 кубитах - результаты точнее классической DFT для малых молекул.
• **Microsoft Azure Quantum**: QFT как стандартный блок в Q# библиотеке; используется в financial optimization и drug discovery сценариях на Azure.

Структура и схема QFT

Классическое быстрое преобразование Фурье (FFT) за O(N log N) выполняет N-точечный DFT. QFT делает то же самое для квантового состояния из n кубитов (N=2^n точек) за O(n^2) квантовых гейтов. Экспоненциальная разница: n=30 кубитов - миллиард состояний, а QFT требует ~450 гейтов.

QFT переводит вычислительный базис в базис Фурье: `QFT|j> = 1/√N * Σ ω^(jk) |k>`, где ω = e^(2πi/N). Схема строится из Hadamard гейтов (создающих суперпозицию) и controlled-phase гейтов R_k (задающих относительные фазы).

Важная оговорка: QFT экспоненциально сжимает вычисления, но результат нельзя «прочитать» напрямую - измерение коллапсирует состояние. QFT полезен только как промежуточный шаг в алгоритмах, где нужна структура фаз, а не конкретные значения. Отсюда его применения: Шор, оценка фаз, поиск скрытой подгруппы.

Quantum Phase Estimation (QPE)

**Quantum Phase Estimation** - один из главных алгоритмов квантовых вычислений. Задача: дан унитарный оператор U и его собственный вектор |ψ>, найти фазу φ: `U|ψ> = e^(2πiφ)|ψ>`. QFT - ключевой элемент QPE.

Схема QPE: (1) подготовить анцилла-регистр в равномерной суперпозиции через Hadamard, (2) применить контролируемые U^(2^k) к анцилла-кубитам - фаза φ кодируется в амплитуды, (3) обратный QFT извлекает φ как двоичное приближение.

QPE - основа алгоритма Шора: период r функции a^x mod N является собственным значением оператора модульного умножения. QPE также используется в квантовой химии: фаза = энергия молекулы. Google использовал QPE-подобный подход в Hartree-Fock симуляции H2 на 2 кубитах (2020).

Применения QFT в алгоритмах

QFT - не изолированный алгоритм, а строительный блок. Он появляется как ключевой компонент в нескольких важнейших квантовых алгоритмах:

• **Алгоритм Шора**: QPE находит период a^x mod N -> факторизация за O((log N)^3)
• **Quantum Chemistry (VQE + QPE)**: оценка энергии молекул - фаза = основное состояние. Google 2020: энергия H2 точнее классики на 2 кубитах.
• **Quantum Machine Learning (HHL)**: HHL алгоритм для СЛАУ использует QPE для нахождения собственных значений матрицы A. Потенциальное ускорение O(log N) vs O(N).
• **Поиск скрытой подгруппы**: обобщение алгоритма Шора на произвольные группы - основа для дискретного логарифма.
• **Квантовая метрология**: QPE позволяет измерять физические величины с точностью O(1/N) против O(1/√N) классически.

HHL алгоритм (Harvard, MIT, 2009) обещал экспоненциальное ускорение для решения систем линейных уравнений. Позднее анализ выявил существенные ограничения: данные должны быть в квантовой памяти (qRAM), матрица - разреженной и хорошо обусловленной. На практике speedup значительно меньше заявленного.

Практическая реализация на реальном железе

QFT на реальных NISQ-процессорах (Noisy Intermediate-Scale Quantum) работает хуже теории из-за шума. Controlled-phase гейты особенно подвержены декогеренции. На IBM Quantum с 127-кубитным Eagle: QFT для n=5 работает с точностью ~85%, для n=10 - ~40%.

• **Approximate QFT**: отбросить controlled-phase гейты с малыми углами (|angle| < π/2^m). Для m=4 убираем 40% гейтов при потере точности <1%.
• **Transpilation**: Qiskit/Cirq транслируют QFT в native gates железа (CNOT+u3 для IBM, SYC для Google). Транслированная схема глубже оригинала в 2-3x.
• **Error Mitigation**: Zero-Noise Extrapolation (ZNE) и Probabilistic Error Cancellation улучшают результаты без полноценного QEC.
• **Hardware topology**: не все кубиты соединены. IBM Eagle - heavy-hex граф. Свопы добавляют гейты и шум.

Google в 2019 году (Quantum Supremacy paper) использовал схему из ~20 слоёв random 2-qubit gates на 53-кубитном Sycamore. QFT не использовался напрямую, но тест проверял возможность выполнения глубоких схем - ключевого условия для QFT в алгоритме Шора.

Ключевые идеи

• **QFT** преобразует n-кубитное состояние за O(n^2) гейтов против O(N log N) = O(2^n * n) классически - экспоненциальное сжатие числа операций.
• **Ограничение**: результат QFT нельзя считать полностью без O(N) измерений, поэтому QFT полезен только как промежуточный шаг в алгоритмах.
• **QPE** использует QFT для извлечения фазы унитарного оператора - основа алгоритма Шора и квантовой химии.
• **NISQ реальность**: шум гейтов ограничивает глубину схемы; Approximate QFT и error mitigation - практические компромиссы.

Связанные темы

QFT - центральный элемент квантовых алгоритмов:

• Алгоритм Шора — QFT - ключевой квантовый шаг в алгоритме Шора для нахождения периода функции a^x mod N
• Квантовая коррекция ошибок — Без QEC глубокие схемы QFT (n=20+) нереализуемы из-за декогеренции; surface code - путь к fault-tolerant QFT

Вопросы для размышления

• QFT создаёт N-компонентную суперпозицию, но измерение даёт один результат. Как алгоритм Шора использует это «ограничение» себе на пользу?
• Approximate QFT отбрасывает малые controlled-phase гейты. Как выбрать оптимальный порог отсечения для конкретного NISQ процессора?
• QPE оценивает фазу с точностью 1/2^n для n анцилла-кубитов. Для RSA-2048 нужно ~2048 анцилла-кубитов только для QPE. Как оптимизировать это требование?

Связанные уроки

• la-06-transformations