通常の Fourier 変換は
\begin{align*}
\hat{f}(y) = \int f(x) e^{2\pi i xy} dy
\end{align*}
と書けるのであった。ここでは書籍との整合性のために、指数部の $-1$ を消している。これを元に、離散 Fourier 変換*1を書くと
\begin{align*}
y_j = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} f(k) e^{2\pi i \frac{kj}{N}}
\end{align*}
という形になる。$x_k := f(k)$ と書くことにすると、
\begin{align*}
y_j = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} x_k e^{2\pi i \frac{kj}{N}}
\end{align*}
となって、書籍の (4.8.1) 式が得られる。つまり、離散 Fourier 変換は列の変換 $\{x_0, \cdots, x_{n-1}\} \to \{y_0, \cdots, y_{n-1}\}$ と見ることができる。
$\omega_N^{kj} = e^{2 \pi i \frac{kj}{N}}$ という記号を導入すると、
\begin{align*}
\sum_{k=0}^{N-1} x_k \ket{k} \xrightarrow{QFT} &\sum_{j=0}^{N-1} y_j \ket{j} \\
= &\sum_{j=0}^{N-1} \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} x_k \omega_N^{kj} \ket{j} \\
= &\sum_{k=0}^{N-1} x_k \sum_{j=0}^{N-1} \frac{1}{\sqrt{N}} \omega_N^{kj} \ket{j}
\end{align*}
と書ける。これは $\sum_{k=0}^{N-1} x_k$ を外すと
\begin{align*}
\ket{k} \xrightarrow{QFT} \sum_{j=0}^{N-1} \frac{1}{\sqrt{N}} \omega_N^{kj} \ket{j}
\end{align*}
と考えることもできるということである。textbook の書き方に倣って
\begin{align*}
\ket{x} \xrightarrow{QFT} \sum_{y=0}^{N-1} \frac{1}{\sqrt{N}} \omega_N^{xy} \ket{y} = \ket{\tilde{x}}
\end{align*}
と書いたほうが見てくれがしっくりくるかもしれない。textbook では更にユニタリ行列としての表示
\begin{align*}
U_{QFT} = \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \frac{1}{\sqrt{N}} \omega_N^{xy} \ket{y} \bra{x}
\end{align*}
を与えている。
*1:離散 Fourier 変換 - らんだむな記憶 で少し遊んでみる。
