by
Vue.jsを使って量子コンピュータの並列演算を再現してみた ~その3~
はじめに
位相推定問題
ざっくり説明すると、
ユニタリ変換Uとその固有状態ψについて、対応する固有値をexp(2πiφ)と置いた時のφ (0 ≦ φ < 1) を求める
というものです。
作ったもの
実際にできたものがこちらになります。
画像内の各番号の機能の説明は以下の通りです。
-
使用するビットの数。最大9ビットまで計算できます。
-
ユニタリ行列。特定のユニタリ変換を行列で表して入力します。画像の0.7071…は1/sqrt(2)のことです。
-
固有状態ψ。ユニタリ行列の固有ベクトルを入力します。
-
論理回路。前半のUが並んでいる部分でユニタリ変換を行い、縦線以降の部分で逆フーリエ変換を行なっています。うまく表現できなかったので省略していますが、1つのUに対して複数回のユニタリ変換を実行しており、n番目のUでは2^n回のユニタリ変換を実行しています。また、ψの部分は1ビットっぽく表示していていますが、実際には複数のビットを使って固有状態ψを表します。ここではそれをまとめて表示している、というつもりです。
-
回路全体の状態。確率が0でない状態のみを表示します。
-
計算結果の確率分布。確率が0でない状態のみを表示します。
-
固有値。回路を実行した結果、得られる固有値の値を表示します。
ちなみに、行列とその固有ベクトルが分かっているなら対応する固有値も簡単に計算できるので、この計算自体にはさほど意味はありません。ただ、この計算を応用することで「ショアのアルゴリズム」という素因数分解を高速に解くアルゴリズムを実装することができます。
書いたコード
GitHubにあげていますので、興味のある方はどうぞ。
動かしてみた
計算を実行すると以下のように計算過程が表示されます。
この例で入力した行列と固有状態に対応する固有値を手計算で求めると
(1+i)/sqrt(2) = 0.707106 + 0.707106 i
となるので、正しく計算できているようです。
おわりに
位相推定問題について、本を読んだだけではいまいちピンと来なかったのですが、自分で実装してみると計算の仕組みなどがよく理解できました。 次回は本文でも少し触れた「ショアのアルゴリズム」を実装してみたいと思います。
おわり