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

候補を絞る構造がない探索で、正解かを判定する回数を減らせるよ。N個から正解1つを探すとき、古典ではO(N)回、量子ではO(√N)回のオラクル呼び出しが目安になる。100万候補なら、理想的な条件で約785回の反復が例だよ。「必ず1000回で見つかる」「実時間がそのまま1000倍速い」という意味ではないんだ。

まず候補の重ね合わせを作る。正解かを判定するオラクルで該当候補の位相を反転し、振幅増幅の操作と組み合わせて、測定で正解が出る確率を高めるんだ。すべての候補の答えを一度に読み出すわけではないよ。反復しすぎると正解の確率が下がるので、回数の選び方も大切なんだ。

適した判定器を量子回路として実装できることが前提だよ。O(√N)は、その判定器を呼ぶ回数の評価で、判定器の構築や実行、ほかの回路操作の費用は別に考える。既存のデータベースへそのまま使えば速くなる、という保証ではなく、問題の構造や必要な回路を評価するんだ。

鍵の総当たり探索にも理論上は使えるよ。kビット鍵の2^k候補に対して、探索の判定回数はO(2^(k/2))になる。ただし、これはAESの安全性が実際に一律半減するという結論とは違う。量子回路の費用や、反復を直列に行う必要と並列化の制約なども関わるんだ。

一律にそう勧めるのは正確ではないよ。NISTのFAQでは、回路の費用や並列化の制約を踏まえ、現在の用途ではAESの128・192・256ビット鍵を引き続き使えると説明している。AESに512ビット鍵の標準がある、という話でもない。実際の暗号の選択や移行は、用途に合う標準や最新の指針で判断するんだ。