第44話 Shor量子計算因数分解アルゴリズム
例として１５を素因数分解して見ます。ただ簡単のため３qubitに制限します。そしてx = 7として周期４が計算される事を確認して見ます。今回は数式だらけですいません。でも淡々と規則どおりにやっているだけなので見た目によらず中学生でもやれる計算です。前回のフローチャートを机上計算してみるという事です。
1,7,4,13のどれかを観測する事になるがこの式を注意深く見てみるとregister2には
x^ζ mod n の値が入っていてある周期rがあります。
x^ζ mod n が繰り返し現れています。x^ζ mod nの数をm(ζ)とすると、
（この例では繰返しm(0)=2, m(1)=2 m(2)=2..m(3)=2で周期r=４）
次のように書き換えることが出来ます。
これは良く見ると、
と書けます。改めてregister2を観測した場合を考えると、あるs(0～3のどれか)で
これを規格化すると、
を観測する事になります。同様にして一般の場合で考えると、
となります。
なので、
となります。
register1を観測すると、ある
を観測する。この確率は
この確率がピークになるのは整数ｚとするとき
の時なので観測されやすい量子状態kとは
の関係があります。これから周期rを求める事ができます。これは観測されやすい量子状態は2^n/r の整数倍となっているとも言えます。また、
とも言えます。
3qubit(x=7)の例では
です。ここで実際に観測される可能性があるのは、
のどれかですが最後(Step5)の量子フーリエ変換後の量子状態の観測確率は、
となっているので実際に観測される可能性が最も高い量子状態は
k=0, 2, 4, 6 だけです。これと周期との関係から次のように推定できます。
でr=4が予測されます。
次回はもう少しこのアルゴリズムの妙技を可視化して見てみたいと思います。
1,7,4,13のどれかを観測する事になるがこの式を注意深く見てみるとregister2には
x^ζ mod n の値が入っていてある周期rがあります。
x^ζ mod n が繰り返し現れています。x^ζ mod nの数をm(ζ)とすると、
（この例では繰返しm(0)=2, m(1)=2 m(2)=2..m(3)=2で周期r=４）
次のように書き換えることが出来ます。
これは良く見ると、
と書けます。改めてregister2を観測した場合を考えると、あるs(0～3のどれか)で
これを規格化すると、
を観測する事になります。同様にして一般の場合で考えると、
となります。
なので、
となります。
register1を観測すると、ある
を観測する。この確率は
この確率がピークになるのは整数ｚとするとき
の時なので観測されやすい量子状態kとは
の関係があります。これから周期rを求める事ができます。これは観測されやすい量子状態は2^n/r の整数倍となっているとも言えます。また、
とも言えます。
3qubit(x=7)の例では
です。ここで実際に観測される可能性があるのは、
のどれかですが最後(Step5)の量子フーリエ変換後の量子状態の観測確率は、
となっているので実際に観測される可能性が最も高い量子状態は
k=0, 2, 4, 6 だけです。これと周期との関係から次のように推定できます。
でr=4が予測されます。
次回はもう少しこのアルゴリズムの妙技を可視化して見てみたいと思います。
