AI要約
グローバーのアルゴリズム中編では、「ハッシュ値が101になる入力」を特定する量子回路を例に、オラクルと振幅増幅の仕組みを解説。遊戯王のルールを借りて、数式を使わない説明をします。
はじめに
前回はグローバーのアルゴリズムのベースの部分を学びました。
今回はいよいよ、ハッシュ化前の生パスワードを見つける仕組みを解説します。
やりたいこと
前回も書きましたが、以下の手順で「ハッシュ化すると101になるビット列」を発見します。
３量子ビット用意する
↓
Hゲートで８通りに重ね合わせる
↓
ハッシュ化する
↓
101の存在確率を上げる
↓
ハッシュ化と逆の作業をする
↓
観測すると「ハッシュ化すると101になるビット列」だけ観測される
遊戯王で流れを見る
「３ビットマン -０００-」を召喚します。ステータスは「存在確率 1.0」です。
魔法カード「Ｈ(アダマール)・ゲート」を発動。自分フィールド上の「３ビットマン」１体を生け贄に捧げ、全８種（０００～１１１）の「３ビットマン」を特殊召喚します。
ここに新たなステップが追加されます。装備魔法「ハッシュ化操作」を発動。フィールドの全てのモンスターに対し、特定のビット操作を行います。ここでは簡単な処理として、「１ビット目を反転する」を適用します。
さらにもう一枚の「ハッシュ化操作」を発動します。今度は「２ビット目を反転する」を適用します。
ここで相手プレーヤーに直接攻撃(ダイレクトアタック)！
相手はトラップカード「フェーズ・キックバック」を発動。フィールド上のモンスターのうち、特定のビット（今回も１０１）を持つモンスターの存在確率の正負が反転します。
さらに相手はトラップカード「ディフュージョン」を発動。フィールド上のモンスターの存在確率の平均値を計算し、各モンスターの存在確率は「平均値の２倍」から「自身の存在確率」を引いた値になります。
ここに新たなステップが追加されます。相手はトラップカード「アンコンピュート」を発動。こちらが装備していたハッシュ化操作が、適用した順番とは逆順に全て破壊されます。
これによって「３ビットマン」たちのビット列が元に戻りました。
最後に1000回のサンプリング（観測）を行います。前回と同様に、各モンスターが観測される回数は各々の存在確率の２乗に比例するため、「ハッシュ化後に101になるモンスター」が25倍も多く観測されるはずです。そのモンスターのビット列こそ、ハッシュ化前の生パスワードであるはずです。
コードで確認
Pythonで実行してみます。
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
#初期化 入力3 + 補助1
qc = QuantumCircuit(4)
#同時計算のため入力ビットを重ね合わせにする
qc.h([0, 1, 2])
#重ね合わせのままハッシュ化する
qc.x(0)
qc.x(1)
#鏡の準備 お作法
qc.x(3)
qc.h(3)
#鏡を特殊な向きに傾けて攻撃を反射させる 暗号文（この場合は'101'）の存在確率だけを反転させる
qc.x(1)
qc.mcx([0, 1, 2], 3) # mcxはccxの拡張バージョン
qc.x(1)
#重ね合わせのままハッシュ化の逆操作を行って平文に戻す ➝ これが出力として観測される
qc.x(1)
qc.x(0)
#ディフュージョン 適当な1ビット（この場合は2番ビット）を標的にして増幅のおまじないをかける
qc.h([0, 1, 2])
qc.x([0, 1, 2])
qc.h(2)
qc.mcx([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')
0111 | 776/1000
0101 | 32/1000
1001 | 33/1000
0001 | 42/1000
1101 | 37/1000
1111 | 28/1000
0011 | 21/1000
1011 | 31/1000「011」が多く観測されました！これがハッシュ化後に「101」になる生のパスワードです。うまくいきましたね！
おわりに
次回はもっと複雑なハッシュ化を解除してみましょう。
