グローバーのアルゴリズム とは？

そうだよ。例えば電話帳に100万人の名前が順番バラバラに載っていて、特定の人を探すとする。普通は最悪100万回めくる必要があるけど、グローバーのアルゴリズムなら約1000回で見つかるんだ。sqrt(100万)=1000だからね

振幅増幅というテクニックを使うんだ。まず量子の重ね合わせで全候補を同時に調べて、正解のデータだけ確率の振幅を少し大きくする。これを何度も繰り返すと、正解の確率がどんどん高まっていく。ちょうど共鳴みたいに正解だけが増幅されるイメージだよ

直接暗号を破るわけではないけど影響はあるよ。例えばAES-256暗号は256ビットの鍵を総当たりで探す必要があるけど、グローバーのアルゴリズムなら探索回数がsqrt(2の256乗)=2の128乗になる。つまり256ビットの安全性が実質128ビット相当に半減するんだ

まさにその通り！AES-128を使っているなら AES-256に、256なら512相当にすれば量子コンピュータにも対抗できる。ショアのアルゴリズムがRSAを根本から破壊するのに対して、グローバーは対称鍵暗号の安全性を半減させるだけだから、対策がシンプルなんだよ

実はグローバーのアルゴリズムは「答えの正しさを判定できる問題」なら何にでも使えるんだ。最適化問題、機械学習のハイパーパラメータ探索、データベースクエリなど応用範囲が広い。二次の高速化は派手じゃないけど、汎用性の高さが魅力で、量子アルゴリズムの中でも最も実用的と言われているよ