量子 Fourier 変換の後で逆量子 Fourier 変換をすると元に戻ることも確認しておきたい。
$$
\begin{align*}
\begin{cases}
\ket{x} \xrightarrow{QFT} \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2\pi i \frac{xy}{N}} \ket{y} \\
\ket{y} \xrightarrow{QFT^{-1}} \frac{1}{\sqrt{N}} \sum_{z=0}^{N-1} e^{-2\pi i \frac{yz}{N}} \ket{z} \\
\end{cases}
\end{align*}
$$
であるので、$QFT$ の後に $QFT^{-1}$ を作用させると、
$$
\begin{align*}
\frac{1}{N} \sum_{z=0}^{N-1} \sum_{y=0}^{N-1} e^{-2\pi i \frac{yz}{N}} e^{2\pi i \frac{xy}{N}} \ket{z} &= \frac{1}{N} \sum_{z=0}^{N-1} \ket{z} \sum_{y=0}^{N-1} e^{2\pi i \frac{(x-z)y}{N}} \\
&= \frac{1}{N} \ket{x} \sum_{y=0}^{N-1} e^{2\pi i \frac{0\cdot y}{N}} + \frac{1}{N} \sum_{z \ne x} \ket{z} \sum_{y=0}^{N-1} e^{2\pi i \frac{(x-z)y}{N}} \\
&= \ket{x} + \frac{1}{N} \sum_{z \ne x} \ket{z} \sum_{y=0}^{N-1} e^{2\pi i \frac{(x-z)y}{N}}
\tag{1}
\end{align*}
$$
を得る。
$\omega = e^{\frac{2 \pi i}{N}}$ と置くと、これは 1 の $N (=2^n)$ 乗根である。$z \ne x$ の時、$v = x-z \neq 0$ と置く。$0 \leq y, y^\prime \leq N-1$ に対して、$vy = vy^\prime \mod N$ とすると、$v(y-y ^\prime) \in N\Z$ となる。
$v$ が奇数の時
$y-y^\prime \in N \Z$ となるが、$-N + 1 \leq y - y\prime \leq N - 1$ なので、$y - y^\prime = 0$ となる。この時、$\omega^{vy}$ に重複がないので、$\{1,\omega^v, \omega^{2v}, \cdots,\omega^{(N-1)v}\} = \{1,\omega, \omega^2, \cdots,\omega^{N-1}\}$ となる。よって、
$$
\begin{align*}
\sum_{y=0}^{N-1} e^{2\pi i \frac{(x-z)y}{N}} = \sum_{y=0}^{N-1} \omega^{vy} = \sum_{y=0}^{N-1} \omega^y = 0
\end{align*}
$$
を得る。
$v$ が偶数の時
$v = 2^\ell\cdot v^\prime$ ($v^\prime$ は奇数) と書けるので、$N^\prime = 2^{n - \ell} < N$ と置くと、$e^{2\pi i \frac{vy}{N}} = e^{2\pi i \frac{v^\prime y}{N^\prime}}$ となる。$\omega = e^{\frac{2 \pi i}{N^\prime}}$ と置き直すと、これは 1 の $N^\prime (=2^{n-\ell})$ 乗根である。上記と同じ理由で $0 \leq y \leq N^\prime - 1$ の範囲では、$\{1,\omega^{v^\prime}, \omega^{2v^\prime}, \cdots,\omega^{(N^\prime-1)v^\prime}\} = \{1,\omega, \omega^2, \cdots,\omega^{N^\prime-1}\}$ である。$N = 2^\ell N^\prime$ であるので、$y$ が 0 から $N - 1$ を動く時、実は $\mod N^\prime$ で見ると、0 から $N^\prime - 1$ を $2^\ell$ 周する。つまり、
$$
\begin{align*}
\{0,\cdots, N - 1\} =\{\underbrace{0,\cdots, N^\prime - 1}_{\text{1st}}, \underbrace{N^\prime,\cdots, 2N^\prime - 1}_{\text{2nd}}, \cdots, \underbrace{2^{\ell-1} N,\cdots, 2^\ell N - 1}_{2^\ell \text{th}}\}
\end{align*}
$$
である。よって、
$$
\begin{align*}
\sum_{y=0}^{N-1} e^{2\pi i \frac{(x-z)y}{N}} = 2^\ell \sum_{y=0}^{N^\prime-1} \omega^{v^\prime y} = 2^\ell \sum_{y=0}^{N^\prime-1} \omega^y = 2^\ell \cdot 0 = 0
\end{align*}
$$
を得る。
以上の結果を (1) 式に代入すると、
$$
\begin{align*}
&\frac{1}{N} \sum_{z=0}^{N-1} \sum_{y=0}^{N-1} e^{-2\pi i \frac{yz}{N}} e^{2\pi i \frac{xy}{N}} \ket{z} = \ket{x} + \frac{1}{N} \sum_{z \ne x} \ket{z} \underbrace{\sum_{y=0}^{N-1} e^{2\pi i \frac{(x-z)y}{N}}}_{= 0} = \ket{x}
\end{align*}
$$
を得る。つまり、$\ket{x} \xrightarrow{QFT^{-1} \circ QFT} \ket{x}$ が示された。
