イノベーション エンジニアブログ


株式会社イノベーションのエンジニアたちの技術系ブログです。ITトレンド・List Finderの開発をベースに、業務外での技術研究などもブログとして発信していってます!


このエントリーをはてなブックマークに追加

Vue.jsを使って量子コンピュータの並列演算を再現してみた ~その4~

はじめに

こんにちは、Yuです。
4回目ですが量子コンピュータのお話です。
よろしければ以前の記事もどうぞ。
その1
その2
その3

前回は位相推定問題を解きました。 今回は「ショアのアルゴリズム」を実装し、素因数分解をさせてみます。

ショアのアルゴリズム

量子コンピュータを使って素因数分解を高速に解くアルゴリズムです。 計算の一部に量子コンピュータを使用します。

作ったもの

実際にできたものがこちらになります。

shor.png

ショアのアルゴリズムの流れは [1] を参照しましたが、 実装したのは量子コンピュータを使う部分以降のみです。 回路部分自体は位相推定問題のものとあまり変わりません。 ユニタリ変換は前回のものとは異なり、
U |y> = |x*y mod M>
です。 逆フーリエ変換を行う前に、問題レジスタ(|1>から始まる部分)を「⓪①」の所で測定し、状態を確定させています。 問題レジスタは1ビットっぽく表示されていますが、実際には解答レジスタ(|0>が並んでいる部分)と同じくらいのビットを使います。 ビット数は最大16まで使用できるように変更しましたが、13ビット以上にすると重すぎてまともに動きません。

書いたコード

GitHubにあげていますので、興味のある方はどうぞ。

動かしてみた

481=13*37を素因数分解してみます。 xには10を指定し、10ビットを使用します。 shor.gif

状態が2^10パターン出てきますが、確率の大きさが波状になっており、 そのピーク(極大値)の数が位数に対応します。 分解対象Mに対してビット数が少ないと、確率が波にならず、位数を求めることができません。 ここでは、ピークの数は6 となりました。 出力結果は37と13になり、確かに素因数分解できています。 もし条件に一致する結果が得られなければ、xを変更して再実行します。

おわりに

ゲートからアルゴリズムまで、 0から全て自分で実装したことで、だいぶ理解が深まった気がします。

その1を書いたときに目標としていた「ショアのアルゴリズム」まで実装することができましたので、このシリーズは今回で終わります。 ありがとうございました。