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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$ .

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

${\displaystyle 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}}}$ .

Свойства

Унитарность

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

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

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

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

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

${\displaystyle 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}},}$

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

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

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

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

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

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

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

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

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

${\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.}$

Например, ${\displaystyle [0.x_{1}]={\frac {x_{1}}{2}}}$ и ${\displaystyle [0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.}$

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

${\displaystyle 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)}$

или

${\displaystyle 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).}$

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

${\displaystyle 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 }$

${\displaystyle ={\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 }$

${\displaystyle ={\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 }$

${\displaystyle ={\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 }$

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

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

Пример

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

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

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

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

${\displaystyle 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}}.}$

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

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

${\displaystyle 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)}$

или

${\displaystyle 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).}$

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

${\displaystyle |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).}$

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

Как подсчитано выше, используется ${\displaystyle n(n+1)/2=6}$ вентилей, что соответствует ${\displaystyle n=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)
• , (англ.) // : 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 —
• , , , , , Lloyd S. , (англ.) // Journal of Chemical Physics / H. Urey , J. E. Mayer , , , — AIP , 2004. — Vol. 121, Iss. 13. — P. 6117—6133. — ISSN ; ; — — —

Ссылки

• от 20 ноября 2020 на Wayback Machine
• от 22 декабря 2018 на Wayback Machine
• от 23 марта 2019 на Wayback Machine
• от 1 января 2019 на Wayback Machine