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

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

Квантовое преобразование Фурье эффективно исполняется на квантовых компьютерах путём специального разложения матрицы в произведение более простых унитарных матриц. С помощью такого разложения, дискретное преобразование Фурье на 2ⁿ входных амплитудах может быть осуществлено квантовой сетью, состоящей из O(n²) вентилей Адамара и контролируемых квантовых вентилей, где n — число кубитов. По сравнению с классическим ДПФ, использующим O(n2ⁿ) элементов памяти (n — количество бит), что экспоненциально больше, чем O(n²) квантовых вентилей КПФ.

Наилучшие из известных алгоритмов квантового преобразования Фурье (по состоянию на конец 2000) задействуют только O(nlog n) вентилей для достижения желаемого приближения результата.

Определение

Квантовое преобразование Фурье — классическое дискретное преобразование Фурье, применённое к вектору амплитуд квантовых состояний. Обычно рассматривают такие вектора, имеющие длину N: = 2ⁿ. Классическое преобразование Фурье действует на вектор (x₀,x₁,…,x_(N-1)) ∈ C ^N и отображает его в вектор (y₀,y₁,…,y_(N-1)) ∈ C ^N по формуле:

y_k = 1/√N∑_(j = 0)^(N-1)x_jω_n^(-jk), k = 0,1,2,…,N-1,

где ω_n = e^(2πi/N) — Nый корень из единицы.

Аналогично, КПФ действует на квантовое состояние |x⟩ = ∑_(i = 0)^(N-1)x_i|i⟩ и отображает его в квантовое состояние ∑_(i = 0)^(N-1)y_i|i⟩ по формуле:

y_k = 1/√N∑_(j = 0)^(N-1)x_jω_n^(jk), k = 0,1,2,…,N-1,

где ω_n та же, что и раньше. Так как ω_n — вращение, обратное преобразование Фурье производится аналогично

y_k = 1/√N∑_(j = 0)^(N-1)x_jω_n^(-jk)

Если x — базисное квантовое состояние, квантовое преобразование Фурье может быть представлено в виде отображения:

QFT(|x⟩) = 1/√N∑_(j = 0)^(N-1)ω_n^(jx)|j⟩

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

F_N = 1/√Nbeginbmatrix1&1&1&1&…&1\1&ω_n&ω_n²&ω_n³&…&ω_n^(N-1)\1&ω_n²&ω_n⁴&ω_n⁶&…&ω_n^(2(N-1))\1&ω_n³&ω_n⁶&ω_n⁹&…&ω_n^(3(N-1))\vdots &vdots &vdots &vdots &&vdots \1&ω_n^(N-1)&ω_n^(2(N-1))&ω_n^(3(N-1))&…&ω_n^((N-1)(N-1))endbmatrix

Поскольку N: = 2ⁿ и ω_n: = e^(2πi/2ⁿ) — простейший (наименьшая по модулю экспоненциальная часть) N-й корень из единицы, для случая N = 4 = 2² и фазы ω₂ = i получаем матрицу преобразования

F₄ = 1/2beginbmatrix1&1&1&1\1&i&-1&-i\1&-1&1&-1\1&-i&-1&iendbmatrix

Свойства

Унитарность

Большинство свойств КПФ следует из того, что данное преобразование унитарно. Этот факт легко проверяется путём умножения матриц FF^(dagger) = F^(dagger)F = I, где F^(dagger) — эрмитово-сопряжённая матрица к F.

Из унитарных свойств следует, что обратное к КПФ преобразование имеет матрицу, эрмитово-сопряжённую к матрице преобразования Фурье, поэтому F⁻¹ = F^(dagger). Если существует эффективная квантовая сеть, осуществляющая КПФ, то эта же сеть может быть запущена в обратную сторону для проведения обратного квантового преобразования Фурье. А это значит, что оба преобразования могут работать эффективно на квантовом компьютере.

Симуляции квантовых сетей двух возможных вариантов 2-кубитового КПФ, использующего F и F⁻¹, показаны для демонстрации идентичного результата (используется Q-Kit).

Построение сетей

Квантовые вентили, используемые в сетях КПФ — вентиль Адамара и вентиль с контролируемой фазой. В терминах матриц

H: = 1/√2beginpmatrix1&1\1&-1endpmatrix, R_m: = beginpmatrix1&0\0&ω_mendpmatrix,

где ω_m: = e^(2πi/2^m) — 2^m-й корень из единицы.

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

Сеть КПФ можно построить для любого числа входных амплитуд N; однако, это проще всего сделать в случае N = 2ⁿ. Тогда получается Ортонормированная система из векторов

|0⟩,…,|2ⁿ-1⟩.

Базисные состояния перечисляют все возможные состояния кубитов:

|x⟩ = |x₁x₂…x_n⟩ = |x₁⟩⊗|x₂⟩⊗…⊗|x_n⟩

где, по правилу тензорного суммирования ⊗, |x_j⟩ означает, что кубит j находится в состоянии x_j, с x_j 0 либо 1. По соглашению, индекс базисного состояния x указывает на возможные состояния этого кубита, то есть является двоичным разложением:

x = x₁2ⁿ⁻¹+x₂2ⁿ⁻²+…+x_n2⁰.

Также удобно использовать дробную двоичную нотацию:

[0.x₁…x_m] = ∑_(k = 1)^mx_k2^(-k).

Например, [0.x₁] = x₁/2 и [0.x₁x₂] = x₁/2+x₂/2².

Используя эти обозначения, КПФ записывается коротко:

QFT(|x₁x₂…x_n⟩) = 1/√N (|0⟩+e^(2πi[0.x_n])|1⟩)⊗(|0⟩+e^(2πi[0.x_(n-1)x_n])|1⟩)⊗…⊗(|0⟩+e^(2πi[0.x₁x₂…x_n])|1⟩)

или

QFT(|x₁x₂…x_n⟩) = 1/√N (|0⟩+ω₁^x|1⟩)⊗(|0⟩+ω₂^x|1⟩)⊗…⊗(|0⟩+ω_n^x|1⟩).

Краткость налицо, представив двоичное разложение обратно в виде суммы

QFT(|x₁x₂…x_n⟩) = 1/√N∑_(k = 0)^(2ⁿ-1)e^(2πik[0.x₁x₂…x_n])|k⟩

= 1/√N∑_({k₀,k₁,...k_(n-1)} ∈ {0,1}ⁿ)e^(2πi∑_(j = 1)ⁿk_(n-j)2^(j-1)[0.x₁x₂…x_n])|k₀k₁…k_(n-1)⟩

= 1/√N∑_({k₀,k₁,...k_(n-1)} ∈ {0,1}ⁿ)∏_(j = 1)ⁿe^(2πik_(n-j)[0.x_jx_(j+1)…x_n])|k₀k₁…k_(n-1)⟩

= 1/√N(|0⟩+e^(2πi[0.x_n])|1⟩)∑_({k₁,...k_(n-1)} ∈ {0,1}ⁿ⁻¹)∏_(j = 1)ⁿ⁻¹e^(2πik_(n-j)[0.x_jx_(j+1)…x_n])|k₁…k_(n-1)⟩

= 1/√N∏_(j = 1)ⁿ(|0⟩+e^(2πi[0.x_jx_(j+1)…x_n])|1⟩)

Видно, что выходной кубит 1 находится в суперпозиции состояний |0⟩ и e^(2πi[0.x₁...x_n])|1⟩, кубит 2 — в суперпозиции |0⟩ и e^(2πi[0.x₂...x_n])|1⟩ и т. д. для остальных кубитов (см. схему-рисунок выше).

Другими словами, ДПФ, операция над n кубитами, может быть разложена в тензорное произведение n однокубитных операций,

Действительно, каждая из таких однокубитных операций эффективным образом реализуется на вентилях с контролируемой фазой и вентилях Адамара. Первый кубит |x₁⟩ потребует один вентиль Адамара и (n-1) вентилей с контролируемой фазой, второй |x₂⟩ потребует два вентиля Адамара и (n-2) вентилей с контролируемой фазой, и так далее (см. схему выше). В итоге потребуется n+(n-1)+…+1 = n(n+1)/2 = O(n²) вентилей, что квадратично полиномиально по отношению к количеству кубитов.

Пример

Рассмотрим квантовое преобразование Фурье на трёх кубитах. Математически оно записывается

QFT:|x⟩↦1/√2³∑_(k = 0)^(2³-1)ω₃^(xk)|k⟩,

где ω₃ — простейший восьмой корень из единицы, удовлетворяющий ω₃⁸ = (e^(2πi/2³))⁸ = 1 (поскольку N = 2³ = 8).

Для сокращения, установим ω: = ω₃, тогда матричное представление КПФ на трёх кубитах

F_(2³) = 1/√2³beginbmatrix1&1&1&1&1&1&1&1\1&ω&ω²&ω³&ω⁴&ω⁵&ω⁶&ω⁷\1&ω²&ω⁴&ω⁶&ω⁸&ω¹⁰&ω¹²&ω¹⁴\1&ω³&ω⁶&ω⁹&ω¹²&ω¹⁵&ω¹⁸&ω²¹\1&ω⁴&ω⁸&ω¹²&ω¹⁶&ω²⁰&ω²⁴&ω²⁸\1&ω⁵&ω¹⁰&ω¹⁵&ω²⁰&ω²⁵&ω³⁰&ω³⁵\1&ω⁶&ω¹²&ω¹⁸&ω²⁴&ω³⁰&ω³⁶&ω⁴²\1&ω⁷&ω¹⁴&ω²¹&ω²⁸&ω³⁵&ω⁴²&ω⁴⁹\endbmatrix = 1/√2³beginbmatrix1&1&1&1&1&1&1&1\1&ω&ω²&ω³&ω⁴&ω⁵&ω⁶&ω⁷\1&ω²&ω⁴&ω⁶&1&ω²&ω⁴&ω⁶\1&ω³&ω⁶&ω&ω⁴&ω⁷&ω²&ω⁵\1&ω⁴&1&ω⁴&1&ω⁴&1&ω⁴\1&ω⁵&ω²&ω⁷&ω⁴&ω&ω⁶&ω³\1&ω⁶&ω⁴&ω²&1&ω⁶&ω⁴&ω²\1&ω⁷&ω⁶&ω⁵&ω⁴&ω³&ω²&ω\endbmatrix.

Это можно упростить, заметив ω⁴ = -1, ω² = i, ω⁶ = -i, ω⁵ = -ω, ω³ = iω и ω⁷ = -iω.

3-кубитное квантовое преобразование Фурье перепишется в виде

QFT(|x₁,x₂,x₃⟩) = 1/√2³ (|0⟩+e^(2πi[0.x₃])|1⟩)⊗(|0⟩+e^(2πi[0.x₂x₃])|1⟩)⊗(|0⟩+e^(2πi[0.x₁x₂x₃])|1⟩)

или

QFT(|x₁,x₂,x₃⟩) = 1/√2³ (|0⟩+ω₁^x|1⟩)⊗(|0⟩+ω₂^x|1⟩)⊗(|0⟩+ω₃^x|1⟩).

Для использования сети составим разложение КПФ в обратном порядке, а именно

|x₁,x₂,x₃⟩longmapsto 1/√2³ (|0⟩+ω₃^x|1⟩)⊗(|0⟩+ω₂^x|1⟩)⊗(|0⟩+ω₁^x|1⟩).

На рисунке ниже представлена сеть для n: = 3 (с обратным порядком выходных кубитов по отношению к прямому КПФ).

Как подсчитано выше, используется n(n+1)/2 = 6 вентилей, что соответствует n = 3.

Кроме того, следующие сети осуществляют 1-, 2- и 3-кубитное КПФ:

Схема и симуляция 1-, 2- и 3-кубитного КПФ Архивная копия от 23 марта 2019 на Wayback Machine

Рисунок демонстрирует два различных исполнения 3-кубитного КПФ, которые эквивалентны.