はじめに
量子フーリエ変換 (Quantum Fourier Transform, QFT) は離散フーリエ変換に対応する量子アルゴリズムです．QFT は量子位相推定や Draper の加算回路など様々な箇所で登場するので，避けては通れない道です．
高速フーリエ変換 (Fast Fourier Transform, FFT) の計算量が O(N \log N) なのに対して，QFT は O(\log N \log \log N) と指数関数的に改善されています．とはいえ，測定によって得られるフーリエ係数は 1 つだけなので，量子アルゴリズムのサブルーチン以外で QFT を使用するメリットはないでしょう．
この記事は，式変形を丁寧に追っていくことで QFT を理解しようという趣旨で書かれています．
離散フーリエ変換の復習
N 次元の複素ベクトル (x_0, x_1, \dots, x_{N-1}) を次のような N 次元の複素ベクトル (y_0, y_1, \dots, y_{N-1}) に移す操作を，離散フーリエ変換といいます．
\begin{equation}
y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2 \pi ijk/N}
\end{equation}
量子フーリエ変換の定義
N=2^n とします．入力の量子状態 \ket{x} と出力の量子状態 \ket{y} を以下のように定義します．
\begin{align}
\ket{x} &= \sum_{j=0}^{2^n - 1} x_j \ket{j}, \\
\ket{y} &= \sum_{k=0}^{2^n - 1} y_k \ket{k}
\end{align}
式 (3) に離散フーリエ変換の定義式 (1) を代入すると，
\begin{equation}
\ket{y} = \sum_{k=0}^{2^n - 1} \left(\frac{1}{2^{n/2}} \sum_{j=0}^{2^n - 1}x_j e^{2\pi ijk/2^n} \right) \ket{k}
\end{equation}
和の順番を入れ替えると，
\begin{equation}
\ket{y} = \sum_{j=0}^{2^n - 1} x_j \left(\frac{1}{2^{n/2}} \sum_{k=0}^{2^n - 1} e^{2\pi ijk/2^n} \ket{k} \right)
\end{equation}
式 (2), (5) を比較すると，\ket{x} \rightarrow \ket{y} は次の変換と同じことだとわかります．
\begin{equation}
\ket{j} \rightarrow \frac{1}{2^{n/2}} \sum_{k=0}^{2^n - 1} e^{2\pi ijk/2^n} \ket{k}
\end{equation}
このような変換を量子フーリエ変換 (Quantum Fourier Transform, QFT) といいます．
量子フーリエ変換の導出
まず，k を k_1 k_2 \cdots k_n と 2 進数表記にします（すなわち，k=k_1 2^{n-1} + k_2 2^{n-2} + \cdots + k_n 2^0）．
\begin{align}
\ket{j} &\rightarrow \frac{1}{2^{n/2}} \sum_{k=0}^{2^n - 1} e^{2\pi ijk/2^n} \ket{k} \\
&= \frac{1}{2^{n/2}} \sum_{k_1=0}^{1} \sum_{k_2=0}^{1} \cdots \sum_{k_n=0}^{1} e^{2\pi ij (k_1 2^{n-1} + k_2 2^{n-2} + \cdots + k_n 2^0)/2^n} \ket{k_1 k_2 \cdots k_n} \\
&= \frac{1}{2^{n/2}} \sum_{k_1=0}^{1} \sum_{k_2=0}^{1} \cdots \sum_{k_n=0}^{1} e^{2\pi ij (k_1 2^{-1} + k_2 2^{-2} + \cdots + k_n 2^{-n})} \ket{k_1 k_2 \cdots k_n}\\
&= \frac{1}{2^{n/2}} \sum_{k_1=0}^{1} \sum_{k_2=0}^{1} \cdots \sum_{k_n=0}^{1} e^{2\pi ij (\sum_{l=1}^{n} k_l 2^{-l})} \ket{k_1 k_2 \cdots k_n} \\
&= \frac{1}{2^{n/2}} \left(\sum_{k_1=0}^{1} e^{2\pi ijk_1 2^{-1}} \ket{k_1} \right) \otimes \cdots \otimes \left(\sum_{k_n=0}^{1} e^{2\pi ijk_n 2^{-n}} \ket{k_n} \right) \\
&= \frac{1}{2^{n/2}} \bigotimes_{l=1}^{n} \left[\sum_{k_l=0}^{1} e^{2\pi ijk_l 2^{-l}} \ket{k_l} \right] \\
&= \frac{1}{2^{n/2}} \bigotimes_{l=1}^{n} \left[\ket{0} + e^{2\pi ij2^{-l}} \ket{1}\right]
\end{align}
ここで，j を j_1 j_2 \cdots j_n と表記し，2 進数の小数で考えると，
\begin{equation}
j 2^{-l} = j_1 j_2 \cdots j_{n-l-1} j_{n-l} . j_{n-l+1} j_{n-l+2} \cdots j_n
\end{equation}
となります．
（例）
\begin{equation}
j 2^{-1} = j_1 j_2 \cdots j_{n-1} .j_{n}
\end{equation}
\begin{equation}
j 2^{-2} = j_1 j_2 \cdots j_{n-2} . j_{n-1} j_{n}
\end{equation}
\begin{equation}
j 2^{-3} = j_1 j_2 \cdots j_{n-3}.j_{n-2} j_{n-1} j_{n}
\end{equation}
式 (14) を e^{2\pi i j 2^{-l}} に代入すると，
\begin{equation}
e^{2\pi i j 2^{-l}} = e^{2\pi i j_1 j_2 \cdots j_{n-l-1} j_{n-l}} \cdot e^{2\pi i 0.j_{n-l+1} j_{n-l+2} \cdots j_n}
\end{equation}
オイラーの公式より，e^{2\pi i m} = \cos (2m\pi) + i \sin (2m\pi) = 1 （m は整数）なので，j2^{-l} の整数部分は無視できて，
\begin{equation}
e^{2\pi i j 2^{-l}} = e^{2\pi i 0.j_{n-l+1} j_{n-l+2} \cdots j_n}
\end{equation}
式 (19) を式 (13) に代入すると，
\begin{align}
&\frac{1}{2^{n/2}} \bigotimes_{l=1}^{n} \left[\ket{0} + e^{2\pi ij2^{-l}} \ket{1}\right] \\
&= \frac{1}{2^{n/2}} \bigotimes_{l=1}^{n} \left[\ket{0} + e^{2\pi i0.j_{n-l+1} j_{n-l+2} \cdots j_n} \ket{1}\right] \\
&= \frac{1}{2^{n/2}} \left(\ket{0} + e^{2\pi i0.j_n} \ket{1}\right) \left(\ket{0} + e^{2\pi i0.j_{n-1}j_n} \ket{1}\right) \cdots \left(\ket{0} + e^{2\pi i0.j_1 \cdots j_n} \ket{1}\right)
\end{align}
以上をまとめると，QFT は次のように書けます．
\begin{equation}
\ket{j_1 j_2 \cdots j_n} \rightarrow \frac{1}{2^{n/2}} \left(\ket{0} + e^{2\pi i0.j_n} \ket{1}\right) \cdots \left(\ket{0} + e^{2\pi i0.j_1 \cdots j_n} \ket{1}\right)
\end{equation}
量子フーリエ変換の構成方法
QFT を構成するために，以下のアダマールゲート H と位相ゲート R_k を使います．
アダマールゲート
アダマールゲート H は次のように定義されます．
\begin{align}
H = \frac{1}{\sqrt{2}}\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
\end{align}
m=0,1 とすると，H ゲートの動作は，
\begin{align}
H\ket{m} &= \frac{1}{\sqrt{2}} \left(\ket{0} + (-1)^{m} \ket{1} \right) \\
&= \frac{1}{\sqrt{2}} \left(\ket{0} + e^{2 \pi i 0.m} \ket{1} \right)
\end{align}
となります．(-1)^m = e^{2 \pi i 0.m} は実際に m を代入することで確認できます．
位相ゲート
位相ゲート R_k は次のように定義されます．
\begin{align}
R_k = \begin{bmatrix}
1 & 0 \\
0 & e^{2\pi i / 2^k}
\end{bmatrix}
\end{align}
R_k の動作は，
\begin{align}
R_k \ket{0} &= \ket{0},\\
R_k \ket{1} &= e^{2\pi i / 2^k} \ket{1}
\end{align}
となります．また，\ket{m} (m=0,1) を制御ビットとした \text{controlled-}R_k ゲートの動作は，
\begin{equation}
\text{controlled-}R_k \ket{1} = \left(e^{2\pi i / 2^k}\right)^m \ket{1} = e^{2\pi i(m/2^{k})} \ket{1}
\end{equation}
となります．
1番目の量子ビットについて
まず，\ket{j_1} に H ゲートを適用します．
\begin{equation}
(H\ket{j_1})\ket{j_2 \cdots j_n} = \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.j_1}\ket{1}) \ket{j_2 \cdots j_n}
\end{equation}
次に，\ket{j_2} を制御ビットとして，\text{controlled-}R_2 ゲートを 1 番目の量子ビットに適用します．
\begin{align}
&\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.j_1} \cdot e^{2\pi i (j_2 / 2^2)}\ket{1}) \ket{j_2 \cdots j_n} \\
&= \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.j_1} \cdot e^{2\pi i 0.0j_2}\ket{1}) \ket{j_2 \cdots j_n} \\
&= \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.j_1j_2}\ket{1}) \ket{j_2 \cdots j_n}
\end{align}
同様にして，\text{controlled-}R_3, R_4, \cdots, R_n ゲートを適用していくと，
\begin{align}
\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.j_1j_2j_3 \cdots j_n}\ket{1}) \ket{j_2 \cdots j_n}
\end{align}
となります．
2番目の量子ビットについて
今度は \ket{j_2} について見ていきます．まず，\ket{j_2} に H ゲートを適用します．
\begin{align}
\frac{1}{2}(\ket{0} + e^{2\pi i0.j_1j_2j_3 \cdots j_n}\ket{1}) (\ket{0} + e^{2\pi i0.j_2} \ket{1})\ket{j_3 \cdots j_n}
\end{align}
次に，\ket{j_3} を制御ビットとして，\text{controlled-}R_2 ゲートを 2 番目の量子ビットに適用します（さきほどと違い，R_k の k が一桁分ずれています）．
\begin{align}
\frac{1}{2}(\ket{0} + e^{2\pi i0.j_1j_2j_3 \cdots j_n}\ket{1}) (\ket{0} + e^{2\pi i0.j_2j_3} \ket{1})\ket{j_3 \cdots j_n}
\end{align}
同様にして，\text{controlled-}R_3, R_4, \cdots, R_{n-1} ゲートを適用していくと，
\begin{align}
\frac{1}{2}(\ket{0} + e^{2\pi i0.j_1j_2j_3 \cdots j_n}\ket{1}) (\ket{0} + e^{2\pi i0.j_2j_3\cdots j_n} \ket{1})\ket{j_3 \cdots j_n}
\end{align}
となります．
まとめ
残りの \ket{j_3 \cdots j_n} についても同じ操作を繰り返すと，最終的に次の状態が得られます．
\begin{align}
\frac{1}{2^{n/2}}(\ket{0} + e^{2\pi i0.j_1\cdots j_n}\ket{1}) (\ket{0} + e^{2\pi i0.j_2 \cdots j_n} \ket{1}) \cdots (\ket{0}+e^{2\pi i0.j_n})
\end{align}
この結果は，式 (23) と比較すると量子ビットの順番が反転しています．そのため，QFT の使い方によってはスワップしてあげる必要があります（場合によってはスワップが必要ないので，適宜見極めなければなりません）．
おまけ
QFT の量子回路の tex ファイルを置いておきます．
qft.tex
\documentclass[uplatex]{jsarticle}
\usepackage{braket}
\usepackage{qcircuit}
\pagestyle{empty}
\begin{document}
\Qcircuit @C=1em @R=1em {
\lstick{\ket{j_1}} & \gate{H} & \gate{R_2} & \qw & \cdots & & \gate{R_{n-1}} & \gate{R_{n}} & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \rstick{\ket{0} + e^{2\pi i 0.j_1 \cdots j_n} \ket{1}}\\
\lstick{\ket{j_2}} & \qw & \ctrl{-1} & \qw & \cdots & & \qw & \qw & \gate{H} & \qw & \cdots & & \gate{R_{n-2}} & \gate{R_{n-1}} & \qw & \cdots & & \qw & \qw & \qw & \qw & \rstick{\ket{0} + e^{2\pi i 0.j_2 \cdots j_n} \ket{1}}\\
\lstick{\vdots} \\
\lstick{\ket{j_{n-1}}} & \qw & \qw & \qw & \qw & \qw & \ctrl{-3} & \qw & \qw & \qw & \qw & \qw & \ctrl{-2} & \qw & \qw & \cdots & & \gate{H} & \gate{R_2} & \qw & \qw & \rstick{\ket{0} + e^{2\pi i 0.j_{n-1}j_n} \ket{1}}\\
\lstick{\ket{j_{n}}} & \qw & \qw & \qw & \qw & \qw & \qw & \ctrl{-4} & \qw & \qw & \qw & \qw & \qw & \ctrl{-3} & \qw & \cdots & & \qw & \ctrl{-1} & \gate{H} & \qw & \rstick{\ket{0} + e^{2\pi i 0.j_n} \ket{1}}\\
}
\end{document}
Discussion