Grover潜伏
振幅増幅をスライダーで回し、無秩序な重ね合わせから「当たり」を浮かび上がらせる。
Grover アルゴリズム (1996): N 個のうち M 個の解を、未ソート探索なら古典 O(N) のところを O(√(N/M)) で発見する量子アルゴリズム。
|s⟩ の一様重ね合わせから出発し、オラクル U_f（解の振幅を反転）と 拡散演算子 U_s = 2|s⟩⟨s| − I（平均周りに反転）を交互に適用。これを k ≈ (π/4)√(N/M) 回繰り返すと解の振幅が最大になる。
N 16
M (解) 1
k (反復) 0
P(解) 0.0625
最適 3
パラメータ
状態
解の振幅 a0.250
非解振幅 b0.250
角度 θ14.5°
(2k+1)θ/27.2°
sinθ = √(M/N)
P(解) = sin²((2k+1)θ)
k* = ⌊(π/(4θ)) − 1/2⌋
P(解) = sin²((2k+1)θ)
k* = ⌊(π/(4θ)) − 1/2⌋
計測ログ
まだ計測なし
操作
N = 量子ビット数 (探索空間 2ᴺ)、M = 解の数。反復 k をスライダーで動かすと振幅増幅の進行を即時可視化。
Step でオラクル + 拡散の1ラウンド進行。観測 で確率分布から1点をサンプリング。マウスホイールでも k を増減できる。
最適な k は反復過多で振幅が むしろ落ちる ことを観察してみよう。