書籍 p.162 図4-12 をもう少し丁寧に追いかけたい。
$\ket{\omega}$ も $\ket{s}$ も $(\R^2)^{\otimes n}$ のベクトルと見ることができるので、図をこの 2 つが張る 2 次元実ベクトル空間の中の回転と考える。よって、$\ket{\omega^\perp}$ は $\ket{s} + \alpha\ket{\omega} = \ket{s} - \frac{1}{\sqrt{2^n}} \ket{\omega}$ 方向を正の向きとするような軸の単位ベクトルであるとする。$\left|\ket{s} - \frac{1}{\sqrt{2^n}} \ket{\omega} \right|^2 = \braket{s|s} - \frac{2}{\sqrt{2^n}} \braket{s|\omega} + \frac{1}{2^n} \braket{\omega|\omega} = 1 - \frac{2}{2^n} + \frac{1}{2^n} = 1 - \frac{1}{2^n}$ であるので、
$$
\begin{align*}
\ket{\omega^\perp} = \sqrt{1 - \frac{1}{2^n}}^{-1} (\ket{s} - \frac{1}{\sqrt{2^n}} \ket{\omega})
\tag{1}
\end{align*}
$$
と考えることができる。
この時、図で言う $\theta$ を求めたい。
$$
\begin{align*}
\Big|\ket{s}\Big| \left|\ket{s} - \frac{1}{\sqrt{2^n}} \ket{\omega} \right| \cos \frac{\theta}{2} &= \braket{s|s} - \frac{1}{\sqrt{2^n}} \braket{s|\omega} \\
&= 1 - \frac{1}{2^n}
\end{align*}
$$
である。よって、
$$
\begin{align*}
\cos \frac{\theta}{2} = \sqrt{1 - \frac{1}{2^2}}
\end{align*}
$$
を得る。また、倍角の公式 $\cos \theta = 2 \cos^2 \frac{\theta}{2} - 1$ より、
$$
\begin{align*}
\cos \theta = 2\sqrt{1 - \frac{1}{2^2}}^2 - 1 = 1 - \frac{2}{2^n}
\tag{2}
\end{align*}
$$
である。
次に、$\ket{s}$ と $U_s U_f \ket{s}$ の間の角度 $\varphi$ を求めたい。$U_s U_f \ket{s} = \frac{2^n - 4}{2^n} \ket{s} + \frac{2}{\sqrt{2^n}} \ket{\omega}$ であった。よって、
$$
\begin{align*}
\Big|\ket{s}\Big| \left|\frac{2^n - 4}{2^n} \ket{s} + \frac{2}{\sqrt{2^n}} \ket{\omega} \right| \cos \varphi &= \frac{2^n - 4}{2^n} \braket{s|s} + \frac{2}{\sqrt{2^n}} \braket{s|\omega} \\
&= \frac{2^n - 4}{2^n} + \frac{2}{2^n} = \frac{2^n - 1}{2^n} = 1 - \frac{1}{2^n}
\end{align*}
$$
である。一方、
$$
\begin{align*}
\left|\frac{2^n - 4}{2^n} \ket{s} + \frac{2}{\sqrt{2^n}} \ket{\omega} \right|^2 &= \left(\frac{2^n - 4}{2^n}\right)^2 \braket{s|s} + 2 \frac{2^n - 4}{2^n} \frac{2}{\sqrt{2^n}} \braket{s|\omega} + \frac{4}{2^n} \braket{\omega|\omega} \\
&= \frac{4^n - 8\cdot 2^n + 16 + 4\cdot 2^n - 16 + 4 \cdot 2^n}{4^n} = 1
\end{align*}
$$
であるので、
$$
\begin{align*}
\cos \varphi = 1 - \frac{1}{2^n}
\tag{3}
\end{align*}
$$
を得る。よって、(2) 式と (3) 式と図から $\varphi = \theta$ が分かる。
図或いは (1) 式から
$$
\begin{align*}
\ket{s} &= \sqrt{1 - \frac{1}{2^n}} \ket{\omega^\perp} + \frac{1}{\sqrt{2^n}} \ket{\omega} \\
&= \cos \frac{\theta}{2} \ket{\omega^\perp} + \sin \frac{\theta}{2} \ket{\omega}
\end{align*}
$$
が求まる。そして、図から、或いは 3 倍角の公式 $\cos (\frac{3}{2} \theta) = 4 \cos^3 \frac{\theta}{2} - 3 \cos \frac{\theta}{2}$ を使って頑張って計算すると、
$$
\begin{align*}
U_s U_f \ket{s} = \cos \frac{3}{2} \theta \ket{\omega^\perp} + \sin \frac{3}{2} \theta \ket{\omega}
\end{align*}
$$
となるというように、$U_s U_f$ を適用するごとに回転角が $\theta$ ずつ増える。ので、適量作用させると、測定時に $\ket{\omega}$ の確率振幅が 1 に近いような状態を作れます、よって $\omega$ が求まりますと言うのがグローバーのアルゴリズム、或いは量子振幅増幅ということになる。
さて、付属のコードを見てみる。
$U_f \ket{s} = CZ H^{\otimes 2} \ket{0}^{\otimes 2}$ に $U_s$ を適用する直前にバリアを入れてみた。
(2) 式より今回のケースでは $\cos \theta = \frac{1}{2}$ なので、$\theta = \frac{\pi}{3}$ であることが分かる。初期状態で $\ket{s}$ と $\ket{\omega^\perp}$ がなしている角は $\frac{\theta}{2} = \frac{\pi}{6}$ であったので、$U_s U_f$ を 1 回適用すると $U_s U_f \ket{s}$ と $\ket{\omega^\perp}$ がなす角は $\frac{\pi}{6} + \frac{\pi}{3} = \frac{\pi}{2}$ となり、$U_s U_f \ket{s}$ と $\ket{\omega^\perp}$ が直交するはずである。これはつまり、（マイナスを無視してゲートを適用しているので）$-U_s U_f \ket{s} = - \ket{\omega}$ の状態が得られていることになる。要するに、シミュレータでは $\ket{11}$ が確率 1 で観測されるはずで、実際そうなっている。これで p.165 まで完了とする。
