Так как квантовые вычисления имеют дело с унитарными преобразованиями, было бы полезно знать, как реализуются необходимые унитарные преобразования. В этом разделе мы предложим алгоритм проведения за полиномиальное время на квантовом компьютере одного такого унитарного преобразования — дискретного преобразования Фурье. Такое преобразование будет представлено в виде матрицы, столбцы и строки которой пронумерованы в соответствии с состояниями, которые связаны с бинарным представлением целого числа в компьютере. В частности, индекс строк и столбцов начинается с 0 , если противоположное не оговорено.

Это преобразование заключается в следующем. Рассмотрим число $a$, причем $0 \leqslant a<q$ для некоторого $q$. Нам надо произвести преобразование вектора $|a\rangle$ в состояние
\[
\frac{1}{q^{1 / 2}} \sum_{c=0}^{q-1}|c\rangle \exp (2 \pi i a c / q) .
\]

То есть мы должны подействовать унитарной матрицей, элементы которой $(a, c)$ равны $\frac{1}{q^{1 / 2}} \exp (2 \pi i a c / q)$. Это преобразование Фурье — сердце нашего алгоритма, мы обозначим его матрицу как $A_{q}$.

Так как мы будем использовать $A_{q}$ для $q$ экспоненциальной величины (т.е. число битов $q$ растет полиномиально относительно длины входных данных), нам необходимо показать, как это преобразование может быть проведено за полиномиальное время. В этой статье мы дадим простое построение для $A_{q}$, где $q$ — степень двойки, которое было предложено в работах Coppersmith [1994] и Deutsch [см. Ekert and Jozsa, 1995]. Эта конструкция по сути является стандартным алгоритмом быстрого преобразования Фурье (FFT) [Knuth, 1981], адаптированного для квантового компьютера. Приведенное здесь построение впервые предложено в работе [Ekert and Jozsa, 1995]. В более ранней версии этой статьи [Shor, 1994] мы предлагали построение для $A_{q}$, где $q$ принадлежала особому классу сглаженных чисел с небольшими простыми множителями. В действительности, в работе Cleve [1994] показано, как строить $A_{q}$ для сглаженных чисел $q$, чьи простые множители не более $O(\log n)$.

Возьмем $q=2^{l}$, и пусть целое число $a$ представимо в бинарном виде как $\left|a_{l-1} a_{l-2} \ldots a_{0}\right\rangle$. Для реализации квантового преобразования Фурье $A_{q}$ нам понадобятся только два типа квантовых гейтов. Это квантовый гейт $R_{j}$, который действует на $j$-й бит квантового компьютера следующим образом
\[
R_{j}=\begin{array}{c}
|0\rangle \\
|1\rangle
\end{array}\left|\begin{array}{cc}
|0\rangle & |1\rangle \\
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{array}\right|,
\]

и $S_{j, k}$, который действует на два бита на $j$ и $k$ позиции, $j<k$, так:
\[
\left.S_{j, k}=\begin{array}{ccccc}
& |00\rangle & |01\rangle & |10\rangle & |11\rangle \\
|00\rangle & 1 & 0 & 0 & 0 \\
|10\rangle & 0 & 1 & 0 & 0 \\
|11\rangle & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & e^{i \theta_{k-j}}
\end{array} \right\rvert\,,
\]

где $\theta_{k-j}=\pi / 2^{k-j}$. Для того, чтобы реализовать преобразование Фурье, мы используем следующую матрицу (действие осуществляется слева направо)
\[
\begin{array}{c}
R_{l-1} S_{l-2, l-1} R_{l-2} S_{l-3, l-1} S_{l-3, l-2} R_{l-3} \ldots \\
\ldots R_{1} S_{0, l-1} S_{0, l-2} \ldots S_{0,2} S_{0,1} R_{0}
\end{array}
\]

таким образом, мы применяем гейты $R_{j}$ в обратном порядке от $R_{l-1}$ до $R_{0}$, а между $R_{j+1}$ и $R_{j}$ мы применяем все гейты $S_{j, k}$, для которых $k>j$. Например, для трех битов матрицы должны действовать в следующим порядке $R_{2} S_{1,2} R_{1} S_{0,2} S_{0,1} R_{0}$. Таким образом, чтобы произвести преобразование Фурье $A_{q}$, где $q=2^{l}$, нам необходимо $l(l-1) / 2$ квантовых гейтов.

Применяя такую последовате.тьность преобразований, окончательно получим квантовое состояние $\frac{1}{q^{1 / 2}} \sum_{b} \exp (2 \pi i a c / q)|b\rangle$, где $b-$ в некотором смысле «побитно-обратное» к числу $c$, то есть это число в бинарной записи получено побитно чтением числа $c$ справа налево. Следовательно, чтобы получить настоящее квантовое преобразование Фурье, нам необходимо либо делать какие-то дальнейшие вычисления, чтобы развернуть биты числа $|b\rangle$ и получить $|c\rangle$, либо оставить эти биты в покое, а договориться читать их в обратном порядке, либо придумать другую более простую реализацию.

Для того, чтобы показать, что это операция в действительности производит квантовое преобразование Фурье, рассмотрим амплитуду перехода из состояния $|a\rangle=\left|a_{l-1} \ldots a_{0}\right\rangle$ в состояние $|b\rangle=\left|b_{l-1} \ldots b_{0}\right\rangle$. Во-первых, коэффициенты $1 / \sqrt{2}$ в матрице $R$, перемножаясь, образуют множитель $1 / q^{1 / 2}$ перед всем выражением. Таким образом, нам надо беспокоиться только о фазовом множителе $\exp (2 \pi i a c / q)$ в выражении (4.1). Матричные элементы $S_{j, k}$ не изменяют значения ни одного бита, а только изменяют их фазы. Поэтому есть только один способ перевести $j$-й бит из $a_{j}$ в $b_{j}$, используя подходящие внутренние элементы матрицы $R_{j}$. Эти внутренние элементы добавляют числа $\pi$ к фазе, если биты $a_{j}$ и $b_{j}$ содержат 1 , и оставляют все без изменений во всех других случаях. После этого матрица $S_{j, k}$ добавляет число $\pi / 2^{k-j}$ к фазе, если $a_{j}$ и $b_{k}$ содержат 1 , и оставляют все без изменений во всех других случаях. Таким образом, полученная фаза на пути от $|a\rangle$ до $|b\rangle$ имеет вид
\[
\sum_{0 \leqslant j<l} \pi a_{j} b_{j}+\sum_{0 \leqslant j<k<l} \frac{\pi}{2^{k-j}} a_{j} b_{k} .
\]

Это выражение может быть переписано, как
\[
\sum_{0 \leqslant j \leqslant k<l} \frac{\pi}{2^{k-j}} a_{j} b_{k} .
\]

Так как $c$ «побитно-обратное» к числу $b$, это выражение может быть далее переписано как
\[
\sum_{0 \leqslant j \leqslant k<l} \frac{\pi}{2^{k-j}} a_{j} c_{l-1-k} .
\]
Производя следующую подстановку $l-k-1$ для $k$ в этой сумме, мы получим
\[
\sum_{0 \leqslant j+k<l} 2 \pi \frac{2^{j} 2^{k}}{2^{l}} a_{j} c_{k} .
\]

Теперь, так как изменение фазы на $2 \pi$ ее не изменяет, мы получим ту же фазу, как при суммировании по $j$ и $k$, исключая лишь значение $l$, получаем
\[
\sum_{j, k=0}^{l-1} 2 \pi \frac{2^{j} 2^{k}}{2^{l}} a_{j} c_{k}=\frac{2 \pi}{2^{l}} \sum_{j=0}^{l-1} 2^{j} a_{j} \sum_{k=0}^{l-1} 2^{k} c_{k},
\]

где последнее равенство следует из дистрибутивного закона умножения. Теперь, $q=2^{l}$ и
\[
a=\sum_{j=0}^{l-1} 2^{j} a_{j}, \quad c=\sum_{k=0}^{l-1} 2^{k} a_{k},
\]

таким образом выражение (4.9) эквивалентно $2 \pi a c / q$ — фазе амплитуды перехода $|a\rangle \rightarrow|c\rangle$ при преобразовании (4.1).

Когда в гейте $S_{j, k}$ разность $k-j$ велика, см. (4.3), фазовый множитель домножается на очень маленькую величину. Фактически такое домножение будет трудно физически точно провести, и если бы это было необходимо делать при квантовых вычислениях, это стало бы серьезной помехой. К счастью, Копперсмит [Coppersmith, 1994] показал, что можно ввести приближенное преобразование Фурье, в котором будут игнорироваться такие малые вклады в фазовый множитель, но такое приближенное преобразование Фурье вполне достаточно, чтобы также использовать его в алгоритме факторизации. В действительности, эта техника заметно уменьшает число квантовых гейтов, необходимых для проведения (приближенного) преобразования Фурье, исключая большинство гейтов $S_{j, k}$. Недавно Гриффитс и Ниу [1996] показали, что это преобразование Фурье может быть получено при использовании только однобитных гейтов при измерении еденичных битов. Обе эти операции потенциально более легко задействовать в физической системе, чем
двубитные гейты. Тем не менее, использование двубитных гейтов все же необходимо в течение шага факторизации по возведению в степень по модулю и алгоритмов вычисления дискретных логарифмов.