グローバーのアルゴリズムとは？2量子ビットモデルから一般化まで
未整列データベースの探索を2次加速するグローバーのアルゴリズムを、最も単純な2量子ビットの例から、一般のn量子ビットへと一般化しながら解説します。
グローバーのアルゴリズムが解く問題
グローバーのアルゴリズム(1996年、Lov Grover)は、N個の要素からなる未整列
(構造を持たない)データベースの中から、特定の条件を満たす1つの要素を見つける問題を、
O(√N)回のオラクル呼び出しで解く量子アルゴリズムです。古典計算では
平均O(N)回の確認が必要なので、2次(quadratic)の高速化が得られます。
「探したい要素にマークを付ける」役割を果たすのがオラクル
U_fで、マークされた状態の位相を反転させます(U_f|x⟩ = -|x⟩
(xがマーク対象の場合)、それ以外はU_f|x⟩ = |x⟩)。
最も単純な例: 2量子ビット(N=4)の場合
グローバーのアルゴリズムの構造を最もシンプルに理解できるのが、2量子ビット
(N = 2² = 4)の場合です。手順は次の通りです。
-
2つの量子ビットにアダマールゲート
H⊗Hを適用し、4つの基底状態|00⟩, |01⟩, |10⟩, |11⟩の一様な重ね合わせ状態を作る -
オラクル
U_fを適用し、マークされた状態(例えば|10⟩)の 振幅の符号だけを反転させる -
「平均に関する反転(inversion about the mean)」と呼ばれる拡散演算子
U_s = 2|s⟩⟨s| - I(|s⟩は一様重ね合わせ状態)を適用する
N=4の場合、最適な反復回数は
(π/4)√N = (π/4)·2 ≈ 1.57を四捨五入したちょうど1回に
なります。しかもN=4という特殊なケースでは、1回のオラクル適用+拡散演算子の
適用だけで、マークされた状態の振幅がぴったり1(確率100%)まで増幅されます。これは
教科書でグローバーのアルゴリズムを説明する際に2量子ビットの例が好まれる理由で、
「たまたま割り切れる」特別な場合にあたります。
一般のn量子ビット(N=2ⁿ)への一般化
一般にN = 2ⁿ個の要素を扱う場合、オラクルと拡散演算子の1セットを
グローバー反復と呼び、これを最適回数
k ≈ (π/4)√N
だけ繰り返すことで、マークされた状態を検出する確率を最大化できます(N=4の
場合、上で見た通りk=1になります)。この繰り返しは、幾何学的には
「マークされた状態」と「マークされていない状態の一様重ね合わせ」の2つで張られる
2次元平面の中で、状態ベクトルを一定の角度
θ = 2·arcsin(1/√N)
ずつ回転させていく操作として理解できます(振幅増幅、amplitude amplificationと
呼ばれる一般的な技法の特殊な場合に相当します)。回転角θが固定されているため、
反復回数が最適値kから離れるほど、マークされた状態を観測する確率はかえって
下がっていく(回転しすぎてしまう、オーバーシュート)点には注意が必要です。
N=4の場合に確率がちょうど100%になったのは、N=4のとき
θがちょうどπ/3となり、初期状態からマークされた状態までの
角度(π/2弱)を1回の回転でぴったり(近似誤差なく)通過できる、という
数値的な偶然によるものです。一般のNでは、最適反復回数k後の
検出確率は100%にかなり近い値にはなりますが、N=4のような厳密な意味での
「1」にはなりません。
暗号への含意: 対称鍵暗号の実効的な鍵長
グローバーのアルゴリズムは、総当たり攻撃(ブルートフォース)が本質である対称鍵暗号の鍵探索にも
応用できます。鍵空間のサイズをN = 2ⁿ(nビット鍵)とすると、
古典的な総当たりは平均O(2ⁿ⁻¹)回の試行が必要なのに対し、グローバーのアルゴリズムは
O(2^(n/2))回で済みます。つまり、実効的な安全性強度が鍵長の半分に
なるということです。AES-128は
量子コンピュータに対して実効的に64bit相当の安全性強度しか持たなくなるため、NISTがAES-256を
耐量子暗号時代の対称鍵暗号として推奨しているのは、このグローバーのアルゴリズムによる
鍵長半減効果を織り込んだ判断です。
まとめ
- グローバーのアルゴリズムは未整列探索をO(√N)回のオラクル呼び出しで解く、2次の高速化を実現する
- N=4(2量子ビット)の場合、1回の反復で確率100%で解が見つかる特殊なケースになる
- 一般のNでは、最適反復回数(π/4)√Nの振幅増幅により、高い確率で解を見つける
- 対称鍵暗号への応用では、実効的な鍵長が半分になるため、AES-256のような長い鍵長が耐量子暗号時代には推奨される