by
Vue.jsを使って量子コンピュータの並列演算を再現してみた ~その4~
はじめに
ショアのアルゴリズム
量子コンピュータを使って素因数分解を高速に解くアルゴリズムです。 計算の一部に量子コンピュータを使用します。
作ったもの
実際にできたものがこちらになります。
ショアのアルゴリズムの流れは
[1]
を参照しましたが、
実装したのは量子コンピュータを使う部分以降のみです。
回路部分自体は位相推定問題のものとあまり変わりません。
ユニタリ変換は前回のものとは異なり、
U |y> = |x*y mod M>
です。
逆フーリエ変換を行う前に、問題レジスタ（|1>から始まる部分）を「⓪①」の所で測定し、状態を確定させています。
問題レジスタは1ビットっぽく表示されていますが、実際には解答レジスタ（|0>が並んでいる部分）と同じくらいのビットを使います。
ビット数は最大16まで使用できるように変更しましたが、13ビット以上にすると重すぎてまともに動きません。
書いたコード
GitHubにあげていますので、興味のある方はどうぞ。
動かしてみた
481=13*37を素因数分解してみます。
xには10を指定し、10ビットを使用します。
状態が2^10パターン出てきますが、確率の大きさが波状になっており、 そのピーク（極大値）の数が位数に対応します。 分解対象Mに対してビット数が少ないと、確率が波にならず、位数を求めることができません。 ここでは、ピークの数は6 となりました。 出力結果は37と13になり、確かに素因数分解できています。 もし条件に一致する結果が得られなければ、xを変更して再実行します。
おわりに
ゲートからアルゴリズムまで、
0から全て自分で実装したことで、だいぶ理解が深まった気がします。
その1を書いたときに目標としていた「ショアのアルゴリズム」まで実装することができましたので、このシリーズは今回で終わります。 ありがとうございました。