量子コンピュータのハードウェア
並び順に規則のない100万件のデータから条件に合う1件を探すとき、グローバーのアルゴリズムで必要な問い合わせ(オラクルの呼び出し)の回数のオーダーとして、最も近いものはどれか。
- A約20回
- B約1,000回
- C約50万回
答えと解説を見る
正解：B. 約1,000回
古典のコンピュータで1件ずつ調べると、平均で半分の約50万回、最悪で100万回かかります。グローバーのアルゴリズムでは、正解の振幅を少しずつ増幅することで、約 √N 回、正確には (π/4)√N ≈ 785回の繰り返しで高い確率で正解が得られ、オーダーとしては √(100万) = 1,000回程度です。速くなるのは2乗の分だけで、ショアのアルゴリズムのような指数関数的な違いはありません。共通鍵暗号では、鍵の全数探索の回数が 2ⁿ から約 2^(n/2) になるので、鍵の長さを2倍にする(AES-128 から AES-256 にする)ことで対応できると考えられています。
- A. log₂(100万) ≈ 20 で、整列済みのデータに対する二分探索の回数です。規則のないデータには使えません。
- B. 正しい。√(100万) = 1,000 のオーダーです。
- C. 古典のコンピュータで1件ずつ調べたときの平均の回数です。