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

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

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

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

Определение

Квантовое преобразование Фурье — классическое дискретное преобразование Фурье, применённое к вектору амплитуд квантовых состояний. Обычно рассматривают такие вектора, имеющие длину $N:=2^n$. Классическое преобразование Фурье действует на вектор $(x_0,x_1,\dots ,x_{N-1})\in {ℂ}^N$ и отображает его в вектор $(y_0,y_1,\dots ,y_{N-1})\in {ℂ}^N$ по формуле:

$y_k=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{x}_j{\omega }_n^{-jk},k=0,1,2,\dots ,N-1,$

где ${\omega }_n=e^{\frac{2\pi i}{N}}$ — N^ый корень из единицы.

Аналогично, КПФ действует на квантовое состояние $|x⟩=\sum _{i=0}^{N-1}{x}_i|i⟩$ и отображает его в квантовое состояние $\sum _{i=0}^{N-1}{y}_i|i⟩$ по формуле:

$y_k=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{x}_j{\omega }_n^{jk},k=0,1,2,\dots ,N-1,$

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

$y_k=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{x}_j{\omega }_n^{-jk}$

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

$QFT(|x⟩)=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{\omega }_n^{jx}|j⟩$.

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

$F_N=\frac{1}{\sqrt{N}}\left[\begin{array}{cccccc}1& 1& 1& 1& \cdots & 1\\ 1& {\omega }_n& {\omega }_n^2& {\omega }_n^3& \cdots & {\omega }_n^{N-1}\\ 1& {\omega }_n^2& {\omega }_n^4& {\omega }_n^6& \cdots & {\omega }_n^{2(N-1)}\\ 1& {\omega }_n^3& {\omega }_n^6& {\omega }_n^9& \cdots & {\omega }_n^{3(N-1)}\\ ⋮& ⋮& ⋮& ⋮& & ⋮\\ 1& {\omega }_n^{N-1}& {\omega }_n^{2(N-1)}& {\omega }_n^{3(N-1)}& \cdots & {\omega }_n^{(N-1)(N-1)}\end{array}\right]$.

Поскольку $N:=2^n$ и ${\omega }_n:=e^{\frac{2\pi i}{2^n}}$ — простейший (наименьшая по модулю экспоненциальная часть) N-й корень из единицы, для случая $N=4=2^2$ и фазы ${\omega }_2=i$ получаем матрицу преобразования

$F_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$.

Свойства

Унитарность

Симуляция квантовой цепи, состоящей из двух кубитов с использованием Q-Kit

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

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

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

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

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

$H:=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),R_m:=\left(\begin{array}{cc}1& 0\\ 0& {\omega }_m\end{array}\right),$

где ${\omega }_m:=e^{\frac{2\pi i}{2^m}}$ — $2^m$-й корень из единицы.

Квантовая сеть КПФ с n кубитами (инвертированный порядок выходных кубитов). Использует понятие двоичного разложения, введённое ниже.

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

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

$|0⟩,\dots ,|2^n-1⟩.$

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

$|x⟩=|x_1{x}_2\dots x_n⟩=|x_1⟩\otimes |x_2⟩\otimes \cdots \otimes |x_n⟩$

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

$x=x_1{2}^{n-1}+x_2{2}^{n-2}+\cdots +x_n{2}^0.$

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

$[0.x_1\dots x_m]=\sum _{k=1}^m{x}_k{2}^{-k}.$

Например, $[0.x_1]=\frac{x_1}{2}$ и $[0.x_1{x}_2]=\frac{x_1}{2}+\frac{x_2}{2^2}.$

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

$QFT(|x_1{x}_2\dots x_n⟩)=\frac{1}{\sqrt{N}}(|0⟩+e^{2\pi i[0.x_n]}|1⟩)\otimes (|0⟩+e^{2\pi i[0.x_{n-1}{x}_n]}|1⟩)\otimes \cdots \otimes (|0⟩+e^{2\pi i[0.x_1{x}_2\dots x_n]}|1⟩)$

или

$QFT(|x_1{x}_2\dots x_n⟩)=\frac{1}{\sqrt{N}}(|0⟩+{\omega }_1^x|1⟩)\otimes (|0⟩+{\omega }_2^x|1⟩)\otimes \cdots \otimes (|0⟩+{\omega }_n^x|1⟩).$

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

$QFT(|x_1{x}_2\dots x_n⟩)=\frac{1}{\sqrt{N}}\sum _{k=0}^{2^n-1}{e}^{2\pi ik[0.x_1{x}_2\dots x_n]}|k⟩$

$=\frac{1}{\sqrt{N}}\sum _{\{k_0,k_1,...k_{n-1}\}\in \{0,1{\}}^n}{e}^{2\pi i\sum _{j=1}^n{k}_{n-j}{2}^{j-1}[0.x_1{x}_2\dots x_n]}|k_0{k}_1\dots k_{n-1}⟩$

$=\frac{1}{\sqrt{N}}\sum _{\{k_0,k_1,...k_{n-1}\}\in \{0,1{\}}^n}\prod _{j=1}^n{e}^{2\pi i{k}_{n-j}[0.x_j{x}_{j+1}\dots x_n]}|k_0{k}_1\dots k_{n-1}⟩$

$=\frac{1}{\sqrt{N}}(|0⟩+e^{2\pi i[0.x_n]}|1⟩)\sum _{\{k_1,...k_{n-1}\}\in \{0,1{\}}^{n-1}}\prod _{j=1}^{n-1}{e}^{2\pi i{k}_{n-j}[0.x_j{x}_{j+1}\dots x_n]}|k_1\dots k_{n-1}⟩$

$=\frac{1}{\sqrt{N}}\prod _{j=1}^n(|0⟩+e^{2\pi i[0.x_j{x}_{j+1}\dots x_n]}|1⟩)$

Видно, что выходной кубит 1 находится в суперпозиции состояний $|0⟩$ и $e^{2\pi i[0.x_1...x_n]}|1⟩$, кубит 2 — в суперпозиции $|0⟩$ и $e^{2\pi i[0.x_2...x_n]}|1⟩$ и т. д. для остальных кубитов (см. схему-рисунок выше).

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

Пример

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

$QFT:|x⟩\mapsto \frac{1}{\sqrt{2^3}}\sum _{k=0}^{2^3-1}{\omega }_3^{xk}|k⟩,$

где ${\omega }_3$ — простейший восьмой корень из единицы, удовлетворяющий ${\omega }_3^8={\left(e^{\frac{2\pi i}{2^3}}\right)}^8=1$ (поскольку $N=2^3=8$).

Для сокращения, установим $\omega :={\omega }_3$, тогда матричное представление КПФ на трёх кубитах

$F_{2^3}=\frac{1}{\sqrt{2^3}}\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& \omega & {\omega }^2& {\omega }^3& {\omega }^4& {\omega }^5& {\omega }^6& {\omega }^7\\ 1& {\omega }^2& {\omega }^4& {\omega }^6& {\omega }^8& {\omega }^{10}& {\omega }^{12}& {\omega }^{14}\\ 1& {\omega }^3& {\omega }^6& {\omega }^9& {\omega }^{12}& {\omega }^{15}& {\omega }^{18}& {\omega }^{21}\\ 1& {\omega }^4& {\omega }^8& {\omega }^{12}& {\omega }^{16}& {\omega }^{20}& {\omega }^{24}& {\omega }^{28}\\ 1& {\omega }^5& {\omega }^{10}& {\omega }^{15}& {\omega }^{20}& {\omega }^{25}& {\omega }^{30}& {\omega }^{35}\\ 1& {\omega }^6& {\omega }^{12}& {\omega }^{18}& {\omega }^{24}& {\omega }^{30}& {\omega }^{36}& {\omega }^{42}\\ 1& {\omega }^7& {\omega }^{14}& {\omega }^{21}& {\omega }^{28}& {\omega }^{35}& {\omega }^{42}& {\omega }^{49}\end{array}\right]=\frac{1}{\sqrt{2^3}}\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& \omega & {\omega }^2& {\omega }^3& {\omega }^4& {\omega }^5& {\omega }^6& {\omega }^7\\ 1& {\omega }^2& {\omega }^4& {\omega }^6& 1& {\omega }^2& {\omega }^4& {\omega }^6\\ 1& {\omega }^3& {\omega }^6& \omega & {\omega }^4& {\omega }^7& {\omega }^2& {\omega }^5\\ 1& {\omega }^4& 1& {\omega }^4& 1& {\omega }^4& 1& {\omega }^4\\ 1& {\omega }^5& {\omega }^2& {\omega }^7& {\omega }^4& \omega & {\omega }^6& {\omega }^3\\ 1& {\omega }^6& {\omega }^4& {\omega }^2& 1& {\omega }^6& {\omega }^4& {\omega }^2\\ 1& {\omega }^7& {\omega }^6& {\omega }^5& {\omega }^4& {\omega }^3& {\omega }^2& \omega \end{array}\right].$

Это можно упростить, заметив ${\omega }^4=-1$, ${\omega }^2=i$, ${\omega }^6=-i$, ${\omega }^5=-\omega$, ${\omega }^3=i\omega$ и ${\omega }^7=-i\omega$.

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

$QFT(|x_1,x_2,x_3⟩)=\frac{1}{\sqrt{2^3}}(|0⟩+e^{2\pi i[0.x_3]}|1⟩)\otimes (|0⟩+e^{2\pi i[0.x_2{x}_3]}|1⟩)\otimes (|0⟩+e^{2\pi i[0.x_1{x}_2{x}_3]}|1⟩)$

или

$QFT(|x_1,x_2,x_3⟩)=\frac{1}{\sqrt{2^3}}(|0⟩+{\omega }_1^x|1⟩)\otimes (|0⟩+{\omega }_2^x|1⟩)\otimes (|0⟩+{\omega }_3^x|1⟩).$

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

$|x_1,x_2,x_3⟩⟼\frac{1}{\sqrt{2^3}}(|0⟩+{\omega }_3^x|1⟩)\otimes (|0⟩+{\omega }_2^x|1⟩)\otimes (|0⟩+{\omega }_1^x|1⟩).$

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

КПФ для 3 кубитов (инвертированный порядок выходных кубитов)

Возможная реализация 3-кубитной сети КПФ в Q-Kit

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

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

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

См. также

• Преобразование Фурье

Литература

• К. Р. Партасарати, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, June 2001)
• Прескилл, Джон, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)
• Шаблон:Source
• Шаблон:Source

Ссылки

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover’s Search Algorithm Шаблон:Wayback
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform Шаблон:Wayback
• Q-Kit: Graphical Quantum Circuit Simulator Шаблон:Wayback
• Quirk online life quantum fourier transform Шаблон:Wayback