量子コンピュータでフーリエ変換すると高速フーリエ変換より高速な件

離散フーリエ変換？

離散フーリエ変換とは、フーリエ変換を離散化したものです。おしまい（ぉぃ
……えーと、みんな大好き周波数分解をするためのもので、音声処理とか画像処理とか無線通信とか色々なところで目にする偉いやつです。式はこんな感じです。

y_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} n k}

以下、$N=8$ の場合を追っていきましょう。
$w = e^{\frac{- \pi i}{4}}$ と置くと、下記の行列計算で表せるのが肝です。

\begin{pmatrix}
y_{0} \\
y_{1} \\
y_{2} \\
y_{3} \\
y_{4} \\
y_{5} \\
y_{6} \\
y_{7} \\
\end{pmatrix} = 
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix} \\

高速フーリエ変換！

高速フーリエ変換は、離散フーリエ変換を高速化したものです（ぉ
分割統治法を使ったCooley-Tukey型のアルゴリズムが有名で、左から右に数値を流す回路っぽく書くとこんな感じになります。斜線が交差しているところをバタフライ演算と呼びます。

入力列の順序をビット反転をするのがミソで、たとえば入力の $x_3$ の添字は2進数だと 011なので反転させて110、すなわち0から数えて6番目に置きます。
そのようにして先ほどの行列計算を変形すると、

\begin{pmatrix}
y_{0} \\
y_{1} \\
y_{2} \\
y_{3} \\
y_{4} \\
y_{5} \\
y_{6} \\
y_{7} \\
\end{pmatrix} = 
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{2} & w^{6} & w^{1} & w^{5} & w^{3} & w^{7} \\
w^{0} & w^{8} & w^{4} & w^{12} & w^{2} & w^{10} & w^{6} & w^{14} \\
w^{0} & w^{12} & w^{6} & w^{18} & w^{3} & w^{15} & w^{9} & w^{21} \\
w^{0} & w^{16} & w^{8} & w^{24} & w^{4} & w^{20} & w^{12} & w^{28} \\
w^{0} & w^{20} & w^{10} & w^{30} & w^{5} & w^{25} & w^{15} & w^{35} \\
w^{0} & w^{24} & w^{12} & w^{36} & w^{6} & w^{30} & w^{18} & w^{42} \\
w^{0} & w^{28} & w^{14} & w^{42} & w^{6} & w^{35} & w^{21} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{4} \\
x_{2} \\
x_{6} \\
x_{1} \\
x_{5} \\
x_{3} \\
x_{7} \\
\end{pmatrix}

この8x8行列を $F_8$ と置いて分解すれば、

\begin{align}
F_8 = \ &
\begin{pmatrix}
1 &&&& w^{0} \\
& 1 &&&& w^{1} \\
&& 1 &&&& w^{2} \\
&&& 1 &&&& w^{3} \\
1 &&&& w^{4} \\
& 1 &&&& w^{5} \\
&& 1 &&&& w^{6} \\
&&& 1 &&&& w^{7} \\
\end{pmatrix}
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{2} & w^{6} \\
w^{0} & w^{8} & w^{4} & w^{12} \\
w^{0} & w^{12} & w^{6} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{2} & w^{6} \\
&&&& w^{0} & w^{8} & w^{4} & w^{12} \\
&&&& w^{0} & w^{12} & w^{6} & w^{18} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
1 &&&& w^{0} \\
& 1 &&&& w^{1} \\
&& 1 &&&& w^{2} \\
&&& 1 &&&& w^{3} \\
1 &&&& w^{4} \\
& 1 &&&& w^{5} \\
&& 1 &&&& w^{6} \\
&&& 1 &&&& w^{7} \\
\end{pmatrix}
\begin{pmatrix}
F_4 & \\
& F_4 \\
\end{pmatrix}
\end{align}

となって回路通り、 $N=4$ の高速フーリエ変換を再帰的に呼び出してバタフライ演算を行えば、 $N=8$ の高速フーリエ変換ができることがわかります。

量子フーリエ変換♪

量子フーリエ変換は、離散フーリエ変換を量子コンピュータで行うものです（
量子ゲートの回路で書くとこんな感じになります。

ここで、また $x, y$ の添字を2進数表示して、入力の量子状態を

\newcommand{\ket}[1]{\left| #1 \right\rangle}
\begin{align}
& \sum_{i_0, i_1, i_2 \in \{0, 1\}} x_{i_0 i_1 i_2} \ket{i_0 \ i_1 \ i_2} \\
&= \ x_{000} \ket{000} + x_{001} \ket{001} + x_{010} \ket{010} + x_{011} \ket{011} + x_{100} \ket{100} + x_{101} \ket{101} + x_{110} \ket{110} + x_{111} \ket{111} \\
\end{align}

出力の量子状態を

\begin{align}
& \sum_{j_0, j_1, j_2 \in \{0, 1\}} y_{j_0 j_1 j_2} \ket{j_0 \ j_1 \ j_2} \\
&= \ y_{000} \ket{000} + y_{001} \ket{001} + y_{010} \ket{010} + y_{011} \ket{011} + y_{100} \ket{100} + y_{101} \ket{101} + y_{110} \ket{110} + y_{111} \ket{111} \\
\end{align}

としています。そして実はこの回路、高速フーリエ変換と同等の行列分解を利用しています。
今度は出力の方をビット反転してみると、

\begin{pmatrix}
y_{0} \\
y_{4} \\
y_{2} \\
y_{6} \\
y_{1} \\
y_{5} \\
y_{3} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix}

この8x8行列を $F'_8$ と置いて、高速フーリエ変換の分解を転置すれば、

\begin{align}
F'_8= \ &
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} \\
w^{0} & w^{2} & w^{4} & w^{6} \\
w^{0} & w^{6} & w^{12} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{8} & w^{12} \\
&&&& w^{0} & w^{2} & w^{4} & w^{6} \\
&&&& w^{0} & w^{6} & w^{12} & w^{18} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
w^{0} &&&& w^{4} \\
& w^{1} &&&& w^{5} \\
&& w^{2} &&&& w^{6} \\
&&& w^{3} &&&& w^{7} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& w^{0} \\
&&&&& w^{1} \\
&&&&&& w^{2} \\
&&&&&&& w^{3} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
1 &&&& -1 \\
& 1 &&&& -1 \\
&& 1 &&&& -1 \\
&&& 1 &&&& -1 \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& 1 \\
&&&&&& w^{2} \\
&&&&&&& w^{2} \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& w^{1} \\
&&&&&& 1 \\
&&&&&&& w^{1} \\
\end{pmatrix}
(H \otimes I \otimes I) \\
= \ &
(I \otimes F'_4) \ CR_{- \pi / 2} \ CR_{- \pi / 4} (H \otimes I \otimes I)
\end{align}

となって回路通り、 3個の量子ゲートを通して $N=4$ の量子フーリエ変換を再帰的に呼び出せば、 $N=8$ の量子フーリエ変換ができることがわかります。

高速フーリエ変換 vs. 量子フーリエ変換

ということで、今回紹介した回路について纏めてみると、

	高速フーリエ変換	量子フーリエ変換
再帰呼び出し	2回	1回
支配的な計算単位	複素数の掛け算	量子ゲート
計算量	$\mathcal{O}(N \log N)$	$\mathcal{O}((\log N)^2)$

となり、量子コンピュータの方が計算量安いことが分かりますね。
高速フーリエ変換では2つに分割してそれぞれ再帰していた計算を、1回の末尾再帰で計算できてしまうのがミソで、このあたり量子コンピュータが並列処理に強いと称される所以なのだと思います。

もちろん、これだけで量子フーリエ変換が高速フーリエ変換より優れているということはできなくて、計算単位が異なりますし、量子状態はそのまま測定できませんし、そもそも普通に使える実用的な量子コンピュータはまだ存在しないのですが、それでもオーダーレベルで高速化できることには大きな可能性を感じます。
そして、量子フーリエ変換の応用にかの有名なショアの素因数分解アルゴリズムがあるそうで、素因数分解が高速化できるならRSA暗号を破れるかもしれなくて……、とテンションを上げたところで、量子アルゴリズムの勉強を進めます。はい。