グローバーの探索アルゴリズム

当たりの状態の一様な重ね合わせを $|w⟩=\frac{1}{\sqrt{M}}{\sum }_{x:\text{当たり}}|x⟩$、外れの一様な重ね合わせを $|r⟩=\frac{1}{\sqrt{N-M}}{\sum }_{x:\text{外れ}}|x⟩$ とすると、2 つは直交する単位ベクトルです。初期状態 $|s⟩=\frac{1}{\sqrt{N}}{\sum }_x|x⟩$（$N=2^n$ なら $H^{\otimes n}|0\cdots 0⟩$）は
$$|s⟩=\sqrt{\frac{M}{N}}|w⟩+\sqrt{\frac{N-M}{N}}|r⟩=\sin \theta |w⟩+\cos \theta |r⟩$$
と書けます。つまり $|s⟩$ は $|r⟩$ 軸から角 $\theta$ だけ $|w⟩$ 側に傾いた、実の 2 次元平面上のベクトルです。

1 回の反復 $G=DO$ は 2 つの操作からなります。位相オラクル $O$ は当たりの項の符号だけを反転させる（$|w⟩\to -|w⟩$、$|r⟩\to |r⟩$）ので、この平面では $|r⟩$ 軸に関する折り返しです。拡散操作 $D=2|s⟩⟨s|-I$（回路では $H^{\otimes n}(2|0\cdots 0⟩⟨0\cdots 0|-I)H^{\otimes n}$）は $|s⟩$ 方向の成分を残し、それに垂直な成分の符号を反転するので、$|s⟩$ 軸に関する折り返しです。どちらも $|w⟩,|r⟩$ の平面を平面自身に写します。軸のなす角が $\theta$ の 2 本の直線について続けて折り返すと、角 $2\theta$ の回転になります（平面の折り返し 2 回の合成は、2 本の軸のなす角の 2 倍の回転）。よって $|r⟩$ から測った角は、初めの $\theta$ から 1 回ごとに $2\theta$ ずつ増え、$k$ 回後には $G^k|s⟩=\sin ((2k+1)\theta )|w⟩+\cos ((2k+1)\theta )|r⟩$ です。測定で当たりのどれかが出る確率は $|w⟩$ 成分の 2 乗なので $P_k={\sin }^2((2k+1)\theta )$ となります。$(2k+1)\theta$ が $\frac{\pi }{2}$ に最も近いとき確率が最大になり、$\theta \approx \sqrt{M/N}$（$M\ll N$）なので必要な回数は約 $\frac{\pi }{4}\sqrt{N/M}$ 回です。反復しすぎると $\frac{\pi }{2}$ を通り越して確率は再び下がります。

$M$ がわからず最適な回数を決められないときは、反復回数 $k$ を $0,1,\dots ,m-1$ から等確率に選ぶ方法があります。このときの平均成功確率は期待値 $\bar{P}=\frac{1}{m}{\sum }_{k=0}^{m-1}{\sin }^2((2k+1)\theta )$ で、次のように閉じた形にできます。半角の公式 ${\sin }^{2}a=\frac{1-\cos 2a}{2}$ より $\bar{P}=\frac{1}{2}-\frac{1}{2m}{\sum }_{k=0}^{m-1}\cos ((4k+2)\theta )$。積和の公式 $2\sin A\cos B=\sin (B+A)-\sin (B-A)$ で $A=2\theta$、$B=(4k+2)\theta$ とおくと
$$2\sin 2\theta \cos ((4k+2)\theta )=\sin ((4k+4)\theta )-\sin (4k\theta )$$
なので、$k=0$ から $m-1$ まで足すと隣どうしが打ち消し合い、$2\sin 2\theta {\sum }_{k=0}^{m-1}\cos ((4k+2)\theta )=\sin (4m\theta )-\sin 0=\sin (4m\theta )$ が残ります。$0<\theta <\frac{\pi }{2}$ より $\sin 2\theta \ne 0$ なので割ってよく、
$$\bar{P}=\frac{1}{2}-\frac{\sin (4m\theta )}{4m\sin 2\theta }$$
です。$m$ が大きければ第 2 項は小さくなり（大きさは $\frac{1}{4m\sin 2\theta }$ 以下）、平均成功確率は $\frac{1}{2}$ 程度になります。