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

グローバーのアルゴリズムは、8 個の要素からマークされた項目を 2 回のイテレーションで見つけ出します。その 2 という数値がどこから来るのか、アンド 3 回目を実行すると何が起きるかを解き明かしましょう。

1. 処理が実行される前の状態は一様重ね合わせ状態です。すべての項目が等しい確率を持つため、マークされた項目が占める確率は 1/8 となります。これは古典的なランダム推測と同じであり、パネルにはその点を明確にするために両方が表示されます。

   $$N=8:\text{uniform superposition gives}P=\frac{1}{8}=12.50\%$$

2. グローバーの各イテレーションは、マークされた状態とそれ以外のすべての状態によって張られる 2 次元平面内での固定角の回転です。その角度は振幅に由来し、N = 8 の場合は約 20.7° になります。

   $$\sin \theta =\frac{1}{\sqrt{N}}⟹\theta =20.70^{\circ };P_k={\sin }^2\left((2k+1)\theta \right)$$

3. したがって、確率は上昇して平坦になる曲線ではなく、正弦の 2 乗であり、急激に上昇します：12.5%、続いて 78.1%、そして 94.5% となります。

   $$k=1:78.12\%;k=2:94.53\%;k=3:33.01\%$$

4. 最適な停止ポイントは、回転が 90° に最も近くなる位置であり、これは N の平方根の π/4 倍となります。8 個の項目ではそれが 2.22 となり、イテレーションを小数回行うことはできないため、2 回となります。

   $$k_{\text{opt}}=\lfloor \frac{\pi }{4}\sqrt{N}\rfloor =\lfloor 2.221\rfloor =2$$

5. 3 回目を実行すると回転が行き過ぎてしまいます。確率は 33.0% に低下し、これは 1 回のイテレーション後よりも悪く、初期状態に向かって逆戻りします。

   $$\text{classical}\sim \frac{N}{2}=4\text{queries}\text{vs}O\left(\sqrt{N}\right)=2$$