フーリエ変換を、上で述べた量子論理回路で実行することを考える。
これを量子フーリエ変換と呼ぶ。

有限個の量子ビットを用いるので、離散的なフーリエ変換となる。
$2^n$項の離散的なフーリエ変換を実行するのに、逐次的にわずか$n$回程度の制御Uで
実現できるところがポイントである。

$n=3$の場合を図2.1に示す。始状態は$|0\rangle|0\rangle|0\rangle$とし、
まずそれぞれのビットにアダマール変換を施す。
\begin{align}
|0\rangle|0\rangle|0\rangle \longrightarrow \left( \frac{1}{\sqrt{2}} \right)^3
( |0\rangle +|1\rangle )^3
\end{align}
8個の状態を$|0)=|0\rangle|0\rangle|0\rangle,|1)=|0\rangle|0\rangle|1\rangle,\cdots,|7)=|1\rangle|1\rangle|1\rangle$
とラベルすると、入力は$\sum_{a=0}^7 |a)$と書ける。

さらに補助ビット$|0\rangle$を書き加えて、以下のようになる。
\begin{align}
\left( \frac{1}{\sqrt{2}} \right)^3 \sum_{a=0}^7 |a) |0\rangle
\end{align}
続いて図のように、$|a)$の各ビットを制御ビットとし、
補助ビット$|0\rangle$を標的ビットとした制御U演算がかかる。

補助ビットにかかる演算は
\begin{align}
U(m)|0\rangle = \exp \left(\frac{2\pi i}{2^3}m \right) |0\rangle \\
U(m)|1\rangle = |1\rangle \label{eq:muimi}
\end{align}
この演算は補助ビットの前の係数を変えるだけなので、
補助ビットをはじめ$|0\rangle$にしておけば、ずっと$|0\rangle$のままとなる。
よって(\ref{eq:muimi})は実質意味を持たない。

この制御Uは8個の重ね合わせの状態にかかるので、8個の状態すべてに演算される。
例として$|5)=|1\rangle|0\rangle|1\rangle$について考えてみる。

それぞれのビットが制御ビットとなっているから、
第1ビットと第3ビットのU演算$U(1),U(4)$のみが補助ビット$|0\rangle$にかかり、
$U(2)$は演算されない。

よって、
\begin{align}
|5)|0\rangle = |1\rangle|0\rangle|1\rangle \cdot |0\rangle \longrightarrow & |1\rangle|0\rangle|1\rangle U(1)U(4)|0\rangle \\
=& |1\rangle|0\rangle|1\rangle \exp \left(\frac{2\pi i}{2^3}1 \right) \exp \left(\frac{2\pi i}{2^3}4 \right) |0\rangle \\
=& \exp \left(\frac{2\pi i}{2^3}5 \right) |1\rangle|0\rangle|1\rangle \cdot |0\rangle \\
=& \exp \left(\frac{2\pi i}{2^3}5 \right) |5)|0\rangle
\end{align}
となる。他の項も同様にして変換され、全体としては
\begin{align}
\left( \frac{1}{\sqrt{2}} \right)^3 \sum_{a=0}^7 |a) |0\rangle \longrightarrow
\left( \frac{1}{\sqrt{2}} \right)^3 \sum_{a=0}^7 \exp \left(\frac{2\pi i}{2^3}a \right) |a)|0\rangle
\end{align}
変換される。

この変換に必要なステップ数は、並列して行っているので、
アダマール変換で1ステップ、制御U演算で3ステップで、$1+3\sim 3$ステップ程度で済む。

clip009.jpg

図2.1:量子フーリエ変換(n=3のとき)

一般の$n$ビットの場合のフーリエ変換も同じようにして作ることができて、
補助ビット$|0\rangle$を省いて書けば
\begin{align}
\left( \frac{1}{\sqrt{2}} \right)^n \sum_{a=0}^{2^n-1} \exp \left(\frac{2\pi i}{2^n}a \right) |a)
\end{align}
と書ける。
量子回路も図\ref{fig:fou}を拡張すればよい。

必要なステップ数は、$n=3$の例からわかるように
$\sim n$ステップ程度である。

さらに上の量子フーリエ変換の拡張として、
絡み合った量子フーリエ変換を構成することができる。

$n=3$の場合を図\ref{fig:en}に示す。
重ね合わせ状態をつくっているビット群$|a)$のほかに、
第2ビット群$|c)$を用意する。

この第2ビット群のビット数は$|a)$の方のビット数とそろえておく。
つまり、3ビットの場合には、$|a),|c)$ともに
$|0\rangle|0\rangle|0\rangle$から$|1\rangle|1\rangle|1\rangle$までの8とおりの状態を表す。
この回路によって、
\begin{align}
\left( \frac{1}{2} \right)^3 \sum_{a=0}^7 \sum_{c=0}^7 \exp \left(\frac{2\pi i}{2^3}ac \right) |a)|c\rangle
\end{align}
という状態を作ることができる。
これは、上の量子フーリエ変換の議論と同様に確かめることができる。

この絡み合ったフーリエ変換の構成にかかるステップ数は、
アダマール変換は1ステップ、制御制御U演算が$9=3^2$ステップで、$1+3^2\sim 3^2$程度である。

一般に$n$ビットの場合は
\begin{align}
\left( \frac{1}{2} \right)^n \sum_{a=0}^{2^n-1} \sum_{c=0}^{2^n-1} \exp \left(\frac{2\pi i}{2^n}ac \right) |a)|c\rangle
\end{align}
である。必要なステップ数は$\sim n^2$程度である。

この絡んだ量子フーリエ変換は、
後述するショアによる因数分解のアルゴリズムにおいて重要な役割を果たす。

clip010.jpg

図2.2:絡んだ量子フーリエ変換(n=3のとき)