書籍 p.139 に書かれていることや記号が分りにくいので、計算しながら言わんとすることを検証してみる。簡単のため $n=3$ の場合を見る。
2 つのレジスタが用意されており、$\ket{0}^{\otimes 3}\ket{\psi}$ で初期化されている。これにアダマールゲート $H_1^{\otimes 3}$ を作用させ、
$$
\begin{align*}
&\frac{1}{\sqrt{2^3}}(\ket{0} + \ket{1})^{\otimes 3} \ket{\psi} = \frac{1}{\sqrt{2^3}}\underbrace{(\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1})}_{\text{1st register}} \underbrace{\ket{\psi}}_{\text{2nd register}}
\tag{1}
\end{align*}
$$
を得る。1 番目のレジスタのそれぞれの量子ビットを制御量子ビットとして、ユニタリゲート $U$ を作用させる。条件としては、1 番目のレジスタの $\ell$ 番目 (MSB: $\ell=1$) の量子ビットを制御ビットとするケースでは、$U$ を $2^{3-\ell}$ 回作用させる。
暫定的に、$\ket{*} = (\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1})$ とおいて、(1) 式を
$$
\begin{align*}
\frac{1}{\sqrt{2^3}}(\ket{0} + \ket{1}) \otimes \ket{*}{\ket{\psi}} = \frac{1}{\sqrt{2^3}}(\ket{0}\ket{*}\ket{\psi} + \ket{1}\ket{*}\ket{\psi})
\end{align*}
$$
と書く。まず、第 1 レジスタの第 1 量子ビットを制御ビットとするユニタリゲート $U$ を $2^{3-1} = 4$ 回適用すると、
$$
\begin{align*}
CU^4 \frac{1}{\sqrt{2^3}}(\ket{0}\ket{*}\ket{\psi} + \ket{1}\ket{*}\ket{\psi}) &= CU^3 \frac{1}{\sqrt{2^3}}(\ket{0}\ket{*}\ket{\psi} + \ket{1}\ket{*} U\ket{\psi}) \\
&= CU^3 \frac{1}{\sqrt{2^3}}(\ket{0}\ket{*}\ket{\psi} + \ket{1}\ket{*} e^{2\pi i \theta}\ket{\psi}) \\
&= \frac{1}{\sqrt{2^3}}(\ket{0}\ket{*}\ket{\psi} + e^{8\pi i \theta}\ket{1}\ket{*}\ket{\psi}) \\
&= \frac{1}{\sqrt{2^3}}(\ket{0} + e^{8\pi i \theta}\ket{1}) \otimes \ket{*}\ket{\psi} \\
\end{align*}
$$
を得る。同様に、第 2, 3 量子ビットを制御ビットとするケースも扱い、全てのアダマールゲートを適用すると、
$$
\begin{align*}
&\frac{1}{\sqrt{2^3}}(\ket{0} + e^{8\pi i \theta}\ket{1}) \otimes (\ket{0} + e^{4\pi i \theta} \ket{1}) \otimes (\ket{0} + e^{2\pi i \theta} \ket{1}) \ket{\psi} \\
=\ &\frac{1}{\sqrt{2^3}} \sum_{k=0}^{2^3-1} e^{2\pi i k \theta} \ket{k} \otimes \ket{\psi}
\tag{2}
\end{align*}
$$
を得る。なるほど、書籍の $C-\hat{U}^m $ とは、それぞれの量子ビットを制御ビットとして、必要な回数 $U$ を第 2 レジスタに作用させるという意味のようだ。この記法はどこで説明されているのかはよく分からないし、$\hat{}$ の意味合いも分からないが、ここでは気にしないでおく。
次に、逆量子 Fourier 変換を第 1 レジスタに適用する。つまり、$\ket{k} \xrightarrow{QFT^{-1}} \frac{1}{\sqrt{2^3}} \sum_{x=0}^{2^3-1} e^{-2\pi i \frac{kx}{2^3}} \ket{x}$ を (2) 式に作用させて、
$$
\begin{align*}
\frac{1}{2^3} \sum_{k=0}^{2^3-1} \sum_{x=0}^{2^3-1} e^{2\pi i k \theta} e^{-2\pi i \frac{kx}{2^3}} \ket{x} \otimes \ket{\psi} &= \frac{1}{2^3} \sum_{k=0}^{2^3-1} \sum_{x=0}^{2^3-1} e^{-\frac{2 \pi i k}{2^3} (x - 2^3 \theta)} \ket{x} \otimes \ket{\psi} \\
& = \frac{1}{2^3} \sum_{x=0}^{2^3-1} \ket{x} \otimes \ket{\psi} \sum_{k=0}^{2^3-1} e^{-\frac{2 \pi i k}{2^3} (x - 2^3 \theta)}
\tag{3}
\end{align*}
$$
を得る。
ここで、補題を用意する。
補題 $n \in \N$ とし、$x \in \Z$ とする。この時 $N=2^n$ と置いて、
$$
\begin{align*}
\sum_{y=0}^{N-1} e^{2\pi i \frac{xy}{N}} = 0
\end{align*}
$$
が成立する。${}_\square$
証明は逆量子 Fourier 変換 (2) - らんだむな記憶の後半と同様である。
仮にある $x_0 \in \Z, 0 \leq x_0 \leq 2^3 - 1$ に対して、$\theta = \frac{x_0}{2^3}$ が求める位相であるとする。$x \neq x_0$ の時、補題より
$$
\begin{align*}
\sum_{k=0}^{2^3-1} e^{-\frac{2 \pi i k}{2^3} (x - x_0)} = 0
\end{align*}
$$
が成立する。これを (3) 式に代入して
$$
\begin{align*}
\frac{1}{2^3} \sum_{k=0}^{2^3-1} \sum_{x=0}^{2^3-1} e^{2\pi i k \theta} e^{-2\pi i \frac{kx}{2^3}} \ket{x} \otimes \ket{\psi} = \ket{x_0} \otimes \ket{\psi}
\tag{4}
\end{align*}
$$
を得る。つまり、第 1 レジスタを測定して得られる $x_0$ から $\theta = \frac{x_0}{2^3}$ として位相が求まる。
次に、$\theta \in [0, 1), 2^3 \theta \not\in \Z$ を考える。$x$ が整数であったことを忘れて $0 \leq x < 2^3$ の範囲の実数を動くとし、$f(x) = \frac{1}{2^3} \sum_{k=0}^{2^3-1} e^{-\frac{2 \pi i k}{2^3} (x - 2^3 \theta)}$ と置くと、これは $x$ に関する $C^\infty$ 関数である。$g(x) = |f(x)|^2 = f(x) \overline{f(x)}$ と置くと、これも $C^\infty$ である。$|f(x)|^2 \leq \left( \frac{1}{2^3} \sum_{k=0}^{2^3-1} \left| e^{-\frac{2 \pi i k}{2^3} (x - 2^3 \theta)} \right| \right)^2 = 1$ であるが、これは $\frac{x - 2^3 \theta}{2^3} \in \Z$ で、かつその時のみ最大値 1 が実現される。$ -\theta \leq \frac{x - 2^3 \theta}{2^3} < 1 - \theta$ であるので、$\frac{x_0 - 2^3 \theta}{2^3} \in \Z$ となる $x_0 \in [0, 2^3)$ は $x_0 = 2^3 \theta$ である。
(4) 式に戻ると第 1 レジスタを測定した時の $\ket{x}$ の観測確率は $|f(x)|^2$ であるが、$|f(x)|^2$ の連続性から、先ほど求めた $x_0$ に最も近い $x_1 \in \Z$ で最大になることが期待される。詳細はニールセン&チャンで説明されているらしい。このことから、真の位相の近似値 $\hat{\theta} = \frac{x_1}{2^3}$ が計算できる。
