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

グローバーのアルゴリズムはO(√N)クエリを達成し、これが最適であることが証明されています。各反復は状態をθ ≈ 2/√Nラジアン回転させます。

均等な重ね合わせでは、どの候補も同じごく小さな振幅から始まります。各ラウンドは二つの操作を行います。まずオラクルが目標の振幅の符号を反転させ、次に「平均値まわりの反転」がすべての振幅を平均を軸に折り返します。すると符号を変えた振幅は伸び、残りは縮みます。繰り返すほど目標の確率は1に近づきます。N = 1,000,000 のリストなら、古典的な探索は平均で 500,000 件を調べますが、Grover はおよそ 1,000 回で足ります。

N = 4、つまり2量子ビットの探索では、Grover は速いだけでなく厳密です。たった1回の反復で目標を 100% の確率で当てます。回転角は sin(θ/2) = 1/√N = 1/2 を満たすので θ = 60°、1ステップ後には状態がちょうど (2·1+1)·30° = 90° 回転して目標軸に一致します。量子アルゴリズムが「たぶん正しい」ではなく「必ず正しい」答えを返す、まれな例です。