Курс «Квантовые вычисления». Глава 6. Квантовое преобразование Фурье и оценка фазы

Курс «Квантовые вычисления»

Цели главы. Построить квантовое преобразование Фурье (QFT) — обобщение преобразования Адамара из главы 5 — и на его основе алгоритм оценки фазы. Оба инструмента понадобятся для алгоритма Шора; оценка фазы также лежит в основе ряда алгоритмов моделирования квантовых систем.

6.1. Определение

Напомним классическое дискретное преобразование Фурье: вектор (x₀, …, x_N−1) переводится в вектор (y₀, …, y_N−1) по формуле y_k = N^−1/2 ∑_j x_j·ω^jk, где ω = e^2πi/N — корень из единицы. ДПФ — сердце цифровой обработки сигналов: оно переводит сигнал из временного представления в частотное, обнажая периодичность.

Квантовое преобразование Фурье — тот же линейный оператор, применённый к амплитудам квантового состояния. Для n кубитов, N = 2ⁿ, на базисных состояниях (отождествляем битовые строки с числами от 0 до N−1):

QFT|j⟩ = N^−1/2 ∑_k=0^N−1 e^2πi·jk/N |k⟩.

Матрица QFT унитарна (упражнение 1), поэтому задаёт допустимое квантовое преобразование. При n = 1 формула даёт |0⟩ → (|0⟩+|1⟩)/√2, |1⟩ → (|0⟩−|1⟩)/√2, то есть вентиль Адамара. Тензорная степень H^⊗n — преобразование Фурье над группой (ℤ₂)ⁿ, естественное для XOR-структуры задачи Саймона; QFT размера 2ⁿ — преобразование над циклической группой ℤ_2ⁿ, связанное с обычной арифметической периодичностью.

6.2. Схема

Ключ к эффективной схеме — представление результата в виде произведения. Запишем j в двоичной записи j = j₁j₂…j_n (старший бит первым) и обозначим двоичную дробь 0.j_l…j_n = j_l/2 + j_l+1/4 + …. Тогда прямым вычислением (упражнение 2):

QFT|j⟩ = 2^−n/2 (|0⟩ + e^2πi·0.j_n|1⟩) ⊗ (|0⟩ + e^{2πi·0.j_n−1j_n}|1⟩) ⊗ … ⊗ (|0⟩ + e^{2πi·0.j₁…j_n}|1⟩).

Для базисного входа |j⟩ выход раскладывается в тензорное произведение однокубитных состояний: каждый выходной кубит кодирует соответствующую двоичную дробь в фазе. Для произвольной суперпозиции входов выход QFT вовсе не обязан быть сепарабельным. Формулы на базисных состояниях достаточно, чтобы построить схему, поскольку её действие на остальные состояния определяется линейностью. Используются H и управляемые фазовые повороты

R_k = ⎡ 1        0        ⎤
      ⎣ 0   e^(2πi/2^k)   ⎦

(добавляют младшие цифры 0.…j_m от других кубитов). Схема: для кубита 1 — H, затем управляемые R₂, …, R_n от кубитов 2, …, n; для кубита 2 — H и управляемые R₂, …, R_n−1; и так далее; в конце — SWAP-ы, разворачивающие порядок кубитов (произведение выше выходит «задом наперёд»).

Сложность. Без финальной перестановки схема содержит n вентилей H и n(n−1)/2 управляемых поворотов — всего n(n+1)/2 операций. Разворот порядка добавляет ⌊n/2⌋ вентилей SWAP, так что асимптотика остаётся O(n²). Классическое БПФ обрабатывает явно заданный вектор длины N = 2ⁿ за O(N log N) = O(n·2ⁿ) операций. Прямое сравнение этих оценок, однако, не доказывает экспоненциального ускорения полезной задачи.

6.3. Почему QFT — не «экспоненциально быстрый FFT»

QFT преобразует амплитуды состояния, недоступные непосредственному чтению. Подготовка общего амплитудного состояния из явно заданного классического вектора длины N сама требует порядка N параметров и в общем случае порядка N операций; специальные модели памяти могут изменить стоимость доступа, но не устраняют цену создания и загрузки произвольных данных. На выходе одно измерение также не выдаёт все N коэффициентов. Поэтому QFT не является заменой классическому FFT для общего классического сигнала.

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

6.4. Оценка фазы

Постановка. Дан унитарный оператор U, доступный вместе с управляемыми степенями U^2k, и его собственный вектор |u⟩: U|u⟩ = e^2πiθ|u⟩. Требуется оценить θ ∈ [0, 1). Сначала разберём случай, когда фаза имеет точную t-битовую запись.

Идея — фазовый откат в чистом виде. Заведём счётный регистр из t кубитов и рабочий регистр в состоянии |u⟩:

1. H^⊗t на счётном регистре: равномерная суперпозиция 2^−t/2∑_x|x⟩|u⟩.
2. Для двоичных разрядов счётного регистра применить управляемые U^2k, k = 0, …, t−1, согласовав разряд с весом 2^k. Рабочий регистр остаётся в собственном состоянии, а фаза e^2πiθ·2k откатывается в управляющий кубит. В результате счётный регистр имеет состояние 2^−t/2∑_x=0^2t−1 e^2πiθx|x⟩.
3. Присмотримся: если θ = j/2^t для целого j, полученное состояние — в точности QFT|j⟩ из раздела 6.1. Применяем обратное QFT (схема из 6.2, прочитанная справа налево) — получаем |j⟩.
4. Измерить счётный регистр. При θ = j/2^t получаем двоичную запись j, то есть θ = 0.j₁j₂…j_t, с вероятностью 1.

Неточный случай. Если θ не представляется конечной t-битовой дробью, выход сосредоточен возле целого 2^tθ. Вероятность получить ближайшую t-битовую дробь не меньше 4/π² ≈ 0,405. Для абсолютной ошибки не более 2^−m с вероятностью отказа не выше ε достаточно взять t = m + ⌈log₂(2 + 1/(2ε))⌉ счётных кубитов. Число верных двоичных разрядов растёт линейно с размером регистра, а абсолютная погрешность убывает экспоненциально.

Стоимость. Обратное QFT требует O(t²) вентилей, но в общей модели главная статья расходов — управляемые степени U. Если строить их повторением U, суммарное число вызовов равно 1 + 2 + 4 + … + 2^t−1 = 2^t − 1; такая зависимость отражает обычную цену оценки фазы с точностью порядка 2^−t. В алгоритме Шора каждое преобразование, соответствующее U^2k, реализуется полиномиальной схемой умножения на заранее вычисленную константу a^2k mod N, а не экспоненциальным числом повторов.

Если вход не является собственным состоянием. Для суперпозиции собственных векторов ∑c_u|u⟩ оценка фазы выдаёт приближение одной из соответствующих фаз, а рабочий регистр проецируется на её собственное подпространство; при невырожденном спектре вероятность равна |c_u|². В алгоритме Шора это позволяет обойтись без приготовления определённого собственного вектора. В задачах квантовой химии тот же принцип используют для оценки энергии, если начальное состояние имеет достаточное перекрытие с нужным собственным состоянием гамильтониана.

Итоги главы

• QFT — унитарный оператор |j⟩ → N^−1/2∑ e^2πijk/N|k⟩; H — его однокубитный случай, слой Адамаров главы 5 — «Фурье по модулю 2».
• Для базисного входа выход QFT раскладывается в тензорное произведение; отсюда получается схема из O(n²) вентилей H, управляемых фазовых поворотов и SWAP.
• Малая схема QFT сама по себе не ускоряет обработку общего явно заданного классического сигнала: нужно учитывать подготовку входа и доступность выходных данных. В квантовых алгоритмах QFT позволяет измерять свойства периодической структуры амплитуд.
• Оценка фазы сочетает фазовый откат управляемых степеней U с обратным QFT; для m точных битов и вероятности отказа ε нужно t = m + O(log(1/ε)) счётных кубитов.

Упражнения

1. Докажите унитарность матрицы QFT: проверьте, что её столбцы попарно ортогональны и нормированы. Указание: сумма геометрической прогрессии ∑_j ω^j(k−k′) равна N при k = k′ и нулю иначе.
2. Выведите произведение-представление из раздела 6.2 для n = 2: раскройте QFT|j₁j₂⟩ по определению и сгруппируйте слагаемые. Выпишите матрицу QFT 4×4.
3. Нарисуйте (или опишите последовательностью вентилей) схему QFT для трёх кубитов. Сколько в ней вентилей H, управляемых поворотов и SWAP?
4. Выполните оценку фазы вручную: U = Z, |u⟩ = |1⟩, счётный регистр из одного кубита. Какое значение фазы будет измерено? Проверьте согласие с Z|1⟩ = e^2πi·(1/2)|1⟩.
5. Тот же вопрос для U = T: сколько кубитов счётного регистра нужно, чтобы измерить фазу точно, и что будет измерено при меньшем регистре?
6. В схеме QFT фазовый поворот R_k при больших k экспоненциально близок к единичной матрице. На этом основано приближённое QFT: повороты с k > O(log n) просто выбрасывают. Оцените, сколько вентилей остаётся, и объясните, почему точность страдает незначительно.

Ответы и указания. 1: скалярное произведение столбцов k и k′ равно N⁻¹∑_j=0^N−1e^{2πij(k−k′)/N} = δ_kk′. 2: при соглашении о положительном знаке показателя QFT₄ = (1/2)[[1,1,1,1],[1,i,−1,−i],[1,−1,1,−1],[1,−i,−1,i]]; произведение однокубитных множителей получается после разворота порядка выходных битов. 3: три H, три управляемых поворота (два R₂, один R₃), один SWAP. 4: счётный кубит проходит H, управляемый Z, H и измеряется в |1⟩ с вероятностью 1; результат 1 означает θ = 0.1₂ = 1/2. 5: θ = 1/8 = 0.001₂, поэтому для точного результата нужны три кубита; при t < 3 получается распределение на соседних t-битовых дробях. 6: если оставить повороты до R_m, остаётся O(nm) вентилей, а накопленная ошибка имеет порядок O(n/2^m); выбор m = O(log(n/ε)) даёт ошибку O(ε) и O(n log(n/ε)) операций.

Литература к главе

1. M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information," гл. 5.1–5.2. Cambridge University Press, 2010.
2. A. Kitaev, "Quantum measurements and the Abelian Stabilizer Problem," 1995. arxiv.org/abs/quant-ph/9511026
3. D. Coppersmith, "An approximate Fourier transform useful in quantum factoring," IBM Research Report, 1994. arxiv.org/abs/quant-ph/0201067

Предыдущая глава || Содержание курса || Следующая глава