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

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

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

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

Определение

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

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{-jk},\quad k=0,1,2,\ldots ,N-1,$

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

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

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{jk},\quad k=0,1,2,\ldots ,N-1,$

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

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{-jk}$

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

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

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

$F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}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)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega _{n}^{N-1}&\omega _{n}^{2(N-1)}&\omega _{n}^{3(N-1)}&\cdots &\omega _{n}^{(N-1)(N-1)}\end{bmatrix}}$.

Поскольку $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}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}$.

См. также: Матрицы Паули

Свойства

Унитарность

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

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

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

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

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

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

$H:={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}},\quad R_{m}:={\begin{pmatrix}1&0\\0&\omega _{m}\end{pmatrix}},$

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

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

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

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

$|0\rangle ,\ldots ,|2^{n}-1\rangle .$

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

$|x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle$

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

$x=x_{1}2^{n-1}+x_{2}2^{n-2}+\cdots +x_{n}2^{0}.\quad$

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

$[0.x_{1}\ldots 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}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right)$

или

$QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +\omega _{1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +\omega _{n}^{x}|1\rangle \right).$

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

$QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\sum _{k=0}^{2^{n}-1}e^{2\pi ik[0.x_{1}x_{2}\ldots x_{n}]}|k\rangle$

$={\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}\ldots x_{n}]}|k_{0}k_{1}\ldots k_{n-1}\rangle$

$={\frac {1}{\sqrt {N}}}\sum _{\{k_{0},k_{1},...k_{n-1}\}\in \{0,1\}^{n}}\prod _{j=1}^{n}e^{2\pi ik_{n-j}[0.x_{j}x_{j+1}\ldots x_{n}]}|k_{0}k_{1}\ldots k_{n-1}\rangle$

$={\frac {1}{\sqrt {N}}}(|0\rangle +e^{2\pi i[0.x_{n}]}|1\rangle )\sum _{\{k_{1},...k_{n-1}\}\in \{0,1\}^{n-1}}\prod _{j=1}^{n-1}e^{2\pi ik_{n-j}[0.x_{j}x_{j+1}\ldots x_{n}]}|k_{1}\ldots k_{n-1}\rangle$

$={\frac {1}{\sqrt {N}}}\prod _{j=1}^{n}(|0\rangle +e^{2\pi i[0.x_{j}x_{j+1}\ldots x_{n}]}|1\rangle )$

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

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

Пример

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

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

где $\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}}}}{\begin{bmatrix}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{bmatrix}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}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{bmatrix}}.$

Это можно упростить, заметив $\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}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right)$

или

$QFT(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +\omega _{1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{3}^{x}|1\rangle \right).$

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

$|x_{1},x_{2},x_{3}\rangle \longmapsto {\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +\omega _{3}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{1}^{x}|1\rangle \right).$

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

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

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

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

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

Рисунок демонстрирует два различных исполнения 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)
• Hales L. R., Hallgren S. An improved quantum Fourier transform algorithm and applications (англ.) // FOCS 2000: 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, USA, 12-14 Nov. 2000. Proceedings — IEEE, 2000. — P. 515—525. — ISBN 978-0-7695-0850-4 — doi:10.1109/SFCS.2000.892005
• Weinstein Y. S., Havel T. F., Emerson J., Boulan N., Saraceno M., Lloyd S., Cory D. G. Quantum process tomography of the quantum Fourier transform (англ.) // Journal of Chemical Physics / H. Urey, J. E. Mayer, Clyde A. Hutchison, Jr., D. Levy, M. I. Lester — AIP, 2004. — Vol. 121, Iss. 13. — P. 6117—6133. — ISSN 0021-9606; 1089-7690; 1520-9032 — doi:10.1063/1.1785151 — PMID:15446906 — arXiv:quant-ph/0406239

Ссылки

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover’s Search Algorithm Архивная копия от 20 ноября 2020 на Wayback Machine
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform Архивная копия от 22 декабря 2018 на Wayback Machine
• Q-Kit: Graphical Quantum Circuit Simulator Архивная копия от 23 марта 2019 на Wayback Machine
• Quirk online life quantum fourier transform Архивная копия от 1 января 2019 на Wayback Machine