Квантовое преобразование Фурье (сокр. КПФ) — линейное преобразование квантовых битов (кубитов ), являющееся квантовым аналогом дискретного преобразования Фурье (ДПФ). КПФ входит во множество квантовых алгоритмов , в особенности в алгоритм Шора разложения числа на множители и вычисления дискретного логарифма , в квантовый алгоритм оценки фазы для нахождения собственных чисел унитарного оператора и алгоритмы для нахождения скрытой подгруппы .
Квантовое преобразование Фурье эффективно исполняется на квантовых компьютерах путём специального разложения матрицы в произведение более простых унитарных матриц . С помощью такого разложения, дискретное преобразование Фурье на 2 n {\displaystyle 2^{n}} входных амплитудах может быть осуществлено квантовой сетью , состоящей из O ( n 2 ) {\displaystyle O(n^{2})} вентилей Адамара и контролируемых квантовых вентилей , где n {\displaystyle n} — число кубитов [1] . По сравнению с классическим ДПФ , использующим O ( n 2 n ) {\displaystyle O(n2^{n})} элементов памяти ( n {\displaystyle n} — количество бит ), что экспоненциально больше, чем O ( n 2 ) {\displaystyle O(n^{2})} квантовых вентилей КПФ.
Наилучшие из известных алгоритмов квантового преобразования Фурье (по состоянию на конец 2000) задействуют только O ( n log n ) {\displaystyle O(n\log n)} вентилей для достижения желаемого приближения результата [2] .
Квантовое преобразование Фурье — классическое дискретное преобразование Фурье, применённое к вектору амплитуд квантовых состояний. Обычно рассматривают такие вектора, имеющие длину N := 2 n {\displaystyle N:=2^{n}} . Классическое преобразование Фурье действует на вектор ( x 0 , x 1 , … , x N − 1 ) ∈ C N {\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}} и отображает его в вектор ( y 0 , y 1 , … , y N − 1 ) ∈ C N {\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}} по формуле :
y k = 1 N ∑ j = 0 N − 1 x j ω n − j k , k = 0 , 1 , 2 , … , N − 1 , {\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,} где ω n = e 2 π i N {\displaystyle \omega _{n}=e^{\frac {2\pi i}{N}}} — N ый корень из единицы .
Аналогично, КПФ действует на квантовое состояние | x ⟩ = ∑ i = 0 N − 1 x i | i ⟩ {\displaystyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle } и отображает его в квантовое состояние ∑ i = 0 N − 1 y i | i ⟩ {\displaystyle \sum _{i=0}^{N-1}y_{i}|i\rangle } по формуле:
y k = 1 N ∑ j = 0 N − 1 x j ω n j k , k = 0 , 1 , 2 , … , N − 1 , {\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,} где ω n {\displaystyle \omega _{n}} та же, что и раньше. Так как ω n {\displaystyle \omega _{n}} — вращение, обратное преобразование Фурье производится аналогично
y k = 1 N ∑ j = 0 N − 1 x j ω n − j k {\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{-jk}} Если x {\displaystyle x} — базисное квантовое состояние , квантовое преобразование Фурье может быть представлено в виде отображения[3] :
Q F T ( | x ⟩ ) = 1 N ∑ j = 0 N − 1 ω n j x | j ⟩ {\displaystyle QFT(|x\rangle )={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}\omega _{n}^{jx}|j\rangle } . КПФ может эквивалентно рассматриваться как унитарная матрица (чем являются квантовые вентили ), действующая на векторы квантовых состояний [4] . Такая матрица F N {\displaystyle F_{N}} имеет не произвольный, а строго определённый вид
F N = 1 N [ 1 1 1 1 ⋯ 1 1 ω n ω n 2 ω n 3 ⋯ ω n N − 1 1 ω n 2 ω n 4 ω n 6 ⋯ ω n 2 ( N − 1 ) 1 ω n 3 ω n 6 ω n 9 ⋯ ω n 3 ( N − 1 ) ⋮ ⋮ ⋮ ⋮ ⋮ 1 ω n N − 1 ω n 2 ( N − 1 ) ω n 3 ( N − 1 ) ⋯ ω n ( N − 1 ) ( N − 1 ) ] {\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}}} . Поскольку N := 2 n {\displaystyle N:=2^{n}} и ω n := e 2 π i 2 n {\displaystyle \omega _{n}:=e^{\frac {2\pi i}{2^{n}}}} — простейший (наименьшая по модулю экспоненциальная часть) N -й корень из единицы , для случая N = 4 = 2 2 {\displaystyle N=4=2^{2}} и фазы ω 2 = i {\displaystyle \omega _{2}=i} получаем матрицу преобразования
F 4 = 1 2 [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 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}}} . Симуляция квантовой цепи, состоящей из двух кубитов с использованием Q-Kit Большинство свойств КПФ следует из того, что данное преобразование унитарно . Этот факт легко проверяется путём умножения матриц F F † = F † F = I {\displaystyle FF^{\dagger }=F^{\dagger }F=I} , где F † {\displaystyle F^{\dagger }} — эрмитово-сопряжённая матрица к F {\displaystyle F} .
Из унитарных свойств следует, что обратное к КПФ преобразование имеет матрицу, эрмитово-сопряжённую к матрице преобразования Фурье, поэтому F − 1 = F † {\displaystyle F^{-1}=F^{\dagger }} . Если существует эффективная квантовая сеть, осуществляющая КПФ, то эта же сеть может быть запущена в обратную сторону для проведения обратного квантового преобразования Фурье. А это значит, что оба преобразования могут работать эффективно на квантовом компьютере.
Симуляции квантовых сетей двух возможных вариантов 2-кубитового КПФ, использующего F {\displaystyle F} и F − 1 {\displaystyle F^{-1}} , показаны для демонстрации идентичного результата (используется Q-Kit ).
Квантовые вентили , используемые в сетях КПФ — вентиль Адамара и вентиль с контролируемой фазой . В терминах матриц
H := 1 2 ( 1 1 1 − 1 ) , R m := ( 1 0 0 ω m ) , {\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}},} где ω m := e 2 π i 2 m {\displaystyle \omega _{m}:=e^{\frac {2\pi i}{2^{m}}}} — 2 m {\displaystyle 2^{m}} -й корень из единицы.
Квантовая сеть КПФ с n кубитами (инвертированный порядок выходных кубитов). Использует понятие двоичного разложения, введённое ниже. В преобразовании используются только линейные квантовые операции, чтобы задание функции для каждого из базисных состояний позволяло определить смешанные состояния из линейности. Это отличается от определения состояний в обычном преобразовании Фурье. Задать преобразование Фурье в обычном смысле — описать то, как получается результат для произвольных входных данных. Но здесь, как и во многих других случаях, проще описать поведение конкретного базисного состояния и вычислять результат из линейности.
Сеть КПФ можно построить для любого числа входных амплитуд N ; однако, это проще всего сделать в случае N = 2 n {\displaystyle N=2^{n}} . Тогда получается Ортонормированная система из векторов
| 0 ⟩ , … , | 2 n − 1 ⟩ . {\displaystyle |0\rangle ,\ldots ,|2^{n}-1\rangle .} Базисные состояния перечисляют все возможные состояния кубитов:
| x ⟩ = | x 1 x 2 … x n ⟩ = | x 1 ⟩ ⊗ | x 2 ⟩ ⊗ ⋯ ⊗ | x n ⟩ {\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 } , | x j ⟩ {\displaystyle |x_{j}\rangle } означает, что кубит j {\displaystyle j} находится в состоянии x j {\displaystyle x_{j}} , с x j {\displaystyle x_{j}} 0 либо 1. По соглашению, индекс базисного состояния x {\displaystyle x} указывает на возможные состояния этого кубита, то есть является двоичным разложением:
x = x 1 2 n − 1 + x 2 2 n − 2 + ⋯ + x n 2 0 . {\displaystyle x=x_{1}2^{n-1}+x_{2}2^{n-2}+\cdots +x_{n}2^{0}.\quad } Также удобно использовать дробную двоичную нотацию:
[ 0. x 1 … x m ] = ∑ k = 1 m x k 2 − k . {\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.} Например, [ 0. x 1 ] = x 1 2 {\displaystyle [0.x_{1}]={\frac {x_{1}}{2}}} и [ 0. x 1 x 2 ] = x 1 2 + x 2 2 2 . {\displaystyle [0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.}
Используя эти обозначения, КПФ записывается коротко[5] :
Q F T ( | x 1 x 2 … 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 1 x 2 … x n ] | 1 ⟩ ) {\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)} или
Q F T ( | x 1 x 2 … x n ⟩ ) = 1 N ( | 0 ⟩ + ω 1 x | 1 ⟩ ) ⊗ ( | 0 ⟩ + ω 2 x | 1 ⟩ ) ⊗ ⋯ ⊗ ( | 0 ⟩ + ω n x | 1 ⟩ ) . {\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).} Краткость налицо, представив двоичное разложение обратно в виде суммы
Q F T ( | x 1 x 2 … x n ⟩ ) = 1 N ∑ k = 0 2 n − 1 e 2 π i k [ 0. x 1 x 2 … x n ] | k ⟩ {\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 } = 1 N ∑ { k 0 , k 1 , . . . k n − 1 } ∈ { 0 , 1 } n e 2 π i ∑ j = 1 n k n − j 2 j − 1 [ 0. x 1 x 2 … x n ] | k 0 k 1 … k n − 1 ⟩ {\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 } = 1 N ∑ { k 0 , k 1 , . . . k n − 1 } ∈ { 0 , 1 } n ∏ j = 1 n e 2 π i k n − j [ 0. x j x j + 1 … x n ] | k 0 k 1 … k n − 1 ⟩ {\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 } = 1 N ( | 0 ⟩ + e 2 π i [ 0. x n ] | 1 ⟩ ) ∑ { k 1 , . . . k n − 1 } ∈ { 0 , 1 } n − 1 ∏ j = 1 n − 1 e 2 π i k n − j [ 0. x j x j + 1 … x n ] | k 1 … k n − 1 ⟩ {\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 } = 1 N ∏ j = 1 n ( | 0 ⟩ + e 2 π i [ 0. x j x j + 1 … x n ] | 1 ⟩ ) {\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 находится в суперпозиции состояний | 0 ⟩ {\displaystyle |0\rangle } и e 2 π i [ 0. x 1 . . . x n ] | 1 ⟩ {\displaystyle e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle } , кубит 2 — в суперпозиции | 0 ⟩ {\displaystyle |0\rangle } и e 2 π i [ 0. x 2 . . . x n ] | 1 ⟩ {\displaystyle e^{2\pi i\,[0.x_{2}...x_{n}]}|1\rangle } и т. д. для остальных кубитов (см. схему-рисунок выше).
Другими словами, ДПФ, операция над n кубитами, может быть разложена в тензорное произведение n однокубитных операций, Действительно, каждая из таких однокубитных операций эффективным образом реализуется на вентилях с контролируемой фазой и вентилях Адамара. Первый кубит | x 1 ⟩ {\displaystyle |x_{1}\rangle } потребует один вентиль Адамара и (n-1) вентилей с контролируемой фазой, второй | x 2 ⟩ {\displaystyle |x_{2}\rangle } потребует два вентиля Адамара и (n-2) вентилей с контролируемой фазой, и так далее (см. схему выше). В итоге потребуется n + ( n − 1 ) + ⋯ + 1 = n ( n + 1 ) / 2 = O ( n 2 ) {\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})} вентилей, что квадратично полиномиально по отношению к количеству кубитов.
Рассмотрим квантовое преобразование Фурье на трёх кубитах. Математически оно записывается
Q F T : | x ⟩ ↦ 1 2 3 ∑ k = 0 2 3 − 1 ω 3 x k | k ⟩ , {\displaystyle QFT:|x\rangle \mapsto {\frac {1}{\sqrt {2^{3}}}}\sum _{k=0}^{2^{3}-1}\omega _{3}^{xk}|k\rangle ,} где ω 3 {\displaystyle \omega _{3}} — простейший восьмой корень из единицы , удовлетворяющий ω 3 8 = ( e 2 π i 2 3 ) 8 = 1 {\displaystyle \omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1} (поскольку N = 2 3 = 8 {\displaystyle N=2^{3}=8} ).
Для сокращения, установим ω := ω 3 {\displaystyle \omega :=\omega _{3}} , тогда матричное представление КПФ на трёх кубитах
F 2 3 = 1 2 3 [ 1 1 1 1 1 1 1 1 1 ω ω 2 ω 3 ω 4 ω 5 ω 6 ω 7 1 ω 2 ω 4 ω 6 ω 8 ω 10 ω 12 ω 14 1 ω 3 ω 6 ω 9 ω 12 ω 15 ω 18 ω 21 1 ω 4 ω 8 ω 12 ω 16 ω 20 ω 24 ω 28 1 ω 5 ω 10 ω 15 ω 20 ω 25 ω 30 ω 35 1 ω 6 ω 12 ω 18 ω 24 ω 30 ω 36 ω 42 1 ω 7 ω 14 ω 21 ω 28 ω 35 ω 42 ω 49 ] = 1 2 3 [ 1 1 1 1 1 1 1 1 1 ω ω 2 ω 3 ω 4 ω 5 ω 6 ω 7 1 ω 2 ω 4 ω 6 1 ω 2 ω 4 ω 6 1 ω 3 ω 6 ω ω 4 ω 7 ω 2 ω 5 1 ω 4 1 ω 4 1 ω 4 1 ω 4 1 ω 5 ω 2 ω 7 ω 4 ω ω 6 ω 3 1 ω 6 ω 4 ω 2 1 ω 6 ω 4 ω 2 1 ω 7 ω 6 ω 5 ω 4 ω 3 ω 2 ω ] . {\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}}.} Это можно упростить, заметив ω 4 = − 1 {\displaystyle \omega ^{4}=-1} , ω 2 = i {\displaystyle \omega ^{2}=i} , ω 6 = − i {\displaystyle \omega ^{6}=-i} , ω 5 = − ω {\displaystyle \omega ^{5}=-\omega } , ω 3 = i ω {\displaystyle \omega ^{3}=i\omega } и ω 7 = − i ω {\displaystyle \omega ^{7}=-i\omega } .
3-кубитное квантовое преобразование Фурье перепишется в виде
Q F T ( | x 1 , x 2 , x 3 ⟩ ) = 1 2 3 ( | 0 ⟩ + e 2 π i [ 0. x 3 ] | 1 ⟩ ) ⊗ ( | 0 ⟩ + e 2 π i [ 0. x 2 x 3 ] | 1 ⟩ ) ⊗ ( | 0 ⟩ + e 2 π i [ 0. x 1 x 2 x 3 ] | 1 ⟩ ) {\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)} или
Q F T ( | x 1 , x 2 , x 3 ⟩ ) = 1 2 3 ( | 0 ⟩ + ω 1 x | 1 ⟩ ) ⊗ ( | 0 ⟩ + ω 2 x | 1 ⟩ ) ⊗ ( | 0 ⟩ + ω 3 x | 1 ⟩ ) . {\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).} Для использования сети составим разложение КПФ в обратном порядке, а именно
| x 1 , x 2 , x 3 ⟩ ⟼ 1 2 3 ( | 0 ⟩ + ω 3 x | 1 ⟩ ) ⊗ ( | 0 ⟩ + ω 2 x | 1 ⟩ ) ⊗ ( | 0 ⟩ + ω 1 x | 1 ⟩ ) . {\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).} На рисунке ниже представлена сеть для n := 3 {\displaystyle n:=3} (с обратным порядком выходных кубитов по отношению к прямому КПФ).
КПФ для 3 кубитов (инвертированный порядок выходных кубитов) Возможная реализация 3-кубитной сети КПФ в Q-Kit Как подсчитано выше, используется n ( n + 1 ) / 2 = 6 {\displaystyle n(n+1)/2=6} вентилей, что соответствует n = 3 {\displaystyle n=3} .
Кроме того, следующие сети осуществляют 1-, 2- и 3-кубитное КПФ: Схема и симуляция 1-, 2- и 3-кубитного КПФ Архивная копия от 23 марта 2019 на Wayback Machine
Рисунок демонстрирует два различных исполнения 3-кубитного КПФ, которые эквивалентны.
↑ Michael A. Nielsen и Исаак Чуан. Quantum Computation and Quantum Information, p. 217 (англ.) . — Cambridge: Cambridge University Press , 2000. — ISBN 0-521-63503-9 . ↑ Hales, Hallgren, 2000 . ↑ Weinstein, Havel, Emerson et al., 2004 . ↑ Ronald de Wolf , The classical and quantum Fourier transform, 1.1 The discrete Fourier transform, p. 1, (pdf) Архивная копия от 12 сентября 2011 на Wayback Machine ↑ Thomas G. Draper, Addition on a Quantum Computer, p. 5, September 1, 1998, (pdf) Архивная копия от 24 декабря 2018 на Wayback Machine К. Р. Партасарати , 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