AI要約
量子コンピュータの代表的な探索アルゴリズム「グローバーのアルゴリズム」を、遊戯王のルールを借りて解説します。前編ではターゲットを特定する「オラクル」の役割を直感的に紐解きます。
はじめに
これまで「量子ゲートで７セグメントLEDを光らせる」「量子ゲートでピクセルアートを作る」というシリーズを公開してきました。
意気揚々と展示会でお披露目したところ、
「既知の答えから途中式を作るのはパズルとしては面白いが、役に立たないのではないか」
というツッコミが左心室の上あたりを貫通しました。ほぼ致命傷です。
「結局、量子コンピュータって何が計算できるの？」という質問は1000回くらい受けています。模範的な回答は、
- 素因数分解ができる（ショアのアルゴリズム）
- 高速検索ができる（グローバーのアルゴリズム）
- 組合せ最適化ができる（QAOA）
- 量子化学計算ができる（VQEなど）
どれどれ、一つ見てみようかな。と検索したら最後。複雑な行列式が画面を覆い尽くし、身は焦げ、燻ぶり、一死以て大悪を誅します（）
そんなわけでこのシリーズでは、グローバーのアルゴリズムを無理やり「遊戯王カード」で説明し、ハッシュ化されたパスワードの解読にチャレンジします。
何がしたい？
まず３量子ビットを用意して、H(アダマール)ゲートで重ね合わせ状態にします。これをそのまま観測すると [000, 001, 010, 011, 100, 101, 110, 111] の８種類が均等な確率で観測されます。
ここに、「101だけ存在確率を上げる」という条件を追加すると、101だけが観測される。これが今回やりたい内容です。
３量子ビット用意する
↓
Hゲートで８通りに重ね合わせる
↓
101の存在確率を上げる
↓
観測すると101だけ観測される
これだけだと何の役に立つかわからないですが、次回、「ハッシュ化されたパスワードのハッシュ化前の状態を見つける」、すなわち生パスワードを解読するタスクに拡張します。
３量子ビット用意する
↓
Hゲートで８通りに重ね合わせる
↓
ハッシュ化する
↓
101の存在確率を上げる
↓
ハッシュ化と逆の作業をする
↓
観測すると「ハッシュ化すると101になるビット列」だけ観測される
なるほど、これこそ我々が求めていた「未知の答えを計算するタスク」ではないか。楽しみである。
遊戯王で流れを見る
「３ビットマン -０００-」を召喚します。ステータスは「存在確率 1.0」です。
魔法カード「Ｈ(アダマール)・ゲート」を発動。自分フィールド上の「３ビットマン」１体を生け贄に捧げ、全８種（０００～１１１）の「３ビットマン」を特殊召喚します。
ここで相手プレーヤーに直接攻撃(ダイレクトアタック)！
しかし相手はトラップカード「フェーズ・キックバック」を発動。フィールド上のモンスターのうち、特定のビット（この場合は１０１）を持つモンスターの存在確率の正負が反転します。
さらに相手はトラップカード「ディフュージョン」を発動。フィールド上のモンスターの存在確率の平均値を計算し、各モンスターの存在確率は「平均値の２倍」から「自身の存在確率」を引いた値になります。（特殊すぎるだろ）
まだバトルフェイズが終わっていない気もしますが、ここで1000回のサンプリング（観測）を行って終わりにします。各モンスターが観測される回数は、各々の存在確率の２乗に比例します。存在確率が0.5と2.5のモンスターは、0.25：6.25＝１：25の回数で観測されるはずです。
コードで確認
一連の流れをPythonとQiskitで実行してみます。
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
#初期化 入力3 + 補助1
qc = QuantumCircuit(4)
#同時計算のため入力ビットを重ね合わせにする
qc.h([0, 1, 2])
#鏡の準備 お作法
qc.x(3)
qc.h(3)
#鏡を特殊な向きに傾けて攻撃を反射させる 暗号文（この場合は'101'）の存在確率だけを反転させる
qc.x(1)
qc.mcx([0, 1, 2], 3) # mcxはccxの拡張バージョン
qc.x(1)
#ディフュージョン 適当な1ビット（この場合は2番ビット）を標的にして増幅のおまじないをかける
qc.h([0, 1, 2])
qc.x([0, 1, 2])
qc.h(2)
qc.ccx(0, 1, 2)
qc.h(2)
qc.x([0, 1, 2])
qc.h([0, 1, 2])
#補助ビットの重ね合わせを解除して解の重複を避ける
qc.h(3)
#計算
qc.measure_all()
backend = AerSimulator(method='matrix_product_state')
t_qc = transpile(qc, backend) #トランスパイルが必要
result = backend.run(t_qc, shots=1000).result().get_counts()
#解の確認
for r in result:
print(f'{r[::-1]} | {result[r]}/1000')
0011 | 25/1000
1011 | 771/1000
1101 | 25/1000
0111 | 32/1000
1001 | 33/1000
0101 | 38/1000
1111 | 38/1000
0001 | 38/1000サンプリング結果は、手前の３ビットが主役、後ろの１ビットが補助ビットです。
あぶり出したかった「101」が771回、その他が30回くらいでした。たしかに指定したパターンが25倍の確率で観測されました。
おわりに
次回は、いくつかのカードを追加してハッシュ化前の値を見つける仕組みを解説します。
