@yuichirominato 2019.02.02更新 45views

【shor】数学苦手なおっさんができるだけ根性で大きな数を素因数分解する旅に出る(その2)


はじめに

数学苦手ですが根性だけでshorをとこうと思っています。前回は全体概要を掴もうとして逆量子フーリエ変換まできました。続きをどんどん書いていきます。

https://blog.mdrft.com/post/2153

逆量子フーリエ変換

結構shorのアルゴリズムを実装するには準備が必要です。逆量子フーリエ変換は最後の求めた量子状態をビットの配列になおすために使います。一応確認すると、shorで何かを解いた時に暗号の周期性に対応するある「角度」が求まります。その角度を高精度で取り出します。

$$iQFT: \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega_n^{xk}\mid k\rangle\mapsto \mid x \rangle \\ \omega_n = e^{\frac{2\pi i}{N}}$$

少しずつわかりやすくしていきたいと思います。量子フーリエ変換の量子回路は、

--H--Rz2--Rz3--Rz4--------------------------
-----*----|----|----H--Rz2--Rz3-------------
----------*----|-------*----|----H--Rz2-----
---------------*------------*-------*----H--

このように、階段状になってます。これは量子状態を作る方のやつなんで、ビットに戻す方の逆量子フーリエ変換は可逆回路で、

----------------------------Rz4--Rz3--Rz2--H----
---------------Rz3--Rz2--H--|----|----*---------
-------Rz2--H--|----*-------|----*--------------
----H--*-------*------------*-------------------

フーリエ変換

やってみます。下記のようになります。

from blueqat import Circuit
import math

Circuit().x[:].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].rz(math.pi/8)[0].cx[2,0].rz(-math.pi/8)[0].cx[2,0].rz(math.pi/16)[0].cx[3,0].rz(-math.pi/16)[0].cx[3,0].h[1].rz(math.pi/4)[1].cx[2,1].rz(-math.pi/4)[1].cx[2,1].rz(math.pi/8)[1].cx[3,1].rz(-math.pi/8)[1].cx[3,1].h[2].rz(math.pi/4)[2].cx[3,2].rz(-math.pi/4)[2].cx[3,2].h[3].run()                                                                    

結果は、

array([ 2.50000000e-01+6.93889390e-18j,  2.30969883e-01-9.56708581e-02j,
        1.76776695e-01-1.76776695e-01j,  9.56708581e-02-2.30969883e-01j,
       -5.55111512e-17-2.50000000e-01j, -9.56708581e-02-2.30969883e-01j,
       -1.76776695e-01-1.76776695e-01j, -2.30969883e-01-9.56708581e-02j,
       -2.50000000e-01-6.93889390e-18j, -2.30969883e-01+9.56708581e-02j,
       -1.76776695e-01+1.76776695e-01j, -9.56708581e-02+2.30969883e-01j,
        5.55111512e-17+2.50000000e-01j,  9.56708581e-02+2.30969883e-01j,
        1.76776695e-01+1.76776695e-01j,  2.30969883e-01+9.56708581e-02j])

わけのわからん量子状態が出てきました。こちらはシミュレータの状態ベクトルというやつです。ちなみにサンプリングで普通に01で出力してみると。。。

from blueqat import Circuit
import math

Circuit().x[:].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].rz(math.pi/8)[0].cx[2,0].rz(-math.pi/8)[0].cx[2,0].rz(math.pi/16)[0].cx[3,0].rz(-math.pi/16)[0].cx[3,0].h[1].rz(math.pi/4)[1].cx[2,1].rz(-math.pi/4)[1].cx[2,1].rz(math.pi/8)[1].cx[3,1].rz(-math.pi/8)[1].cx[3,1].h[2].rz(math.pi/4)[2].cx[3,2].rz(-math.pi/4)[2].cx[3,2].h[3].m[:].run(shots=100)

結果は、

Counter({'0111': 10,
         '0000': 11,
         '1101': 5,
         '0011': 2,
         '1010': 8,
         '1001': 9,
         '1110': 11,
         '1111': 5,
         '1000': 5,
         '1011': 7,
         '0110': 5,
         '0100': 7,
         '0101': 6,
         '0001': 5,
         '1100': 2,
         '0010': 2})

ばらばらの値が出てきました。16通り全て出てきました。これは理論どおりで、量子フーリエ変換は量子状態なので結果を見ることができません。

量子フーリエ変換までの道のりは長そうです。。。最後に回します。

shorの位相推定回路

回路自体は加算器から順番に作り込んで行けばいいみたいです。

加算器は10進数から2進数に下記の記事で変換してみました。

https://blog.blueqat.com/post/2141

使っているのは下記の論文です。

Quantum Networks for Elementary Arithmetic Operations
V. Vedral, A. Barenco, A. Ekert
(Submitted on 16 Nov 1995)
https://arxiv.org/abs/quant-ph/9511018

これによって少しだけ実装が進みました。次はモジュロ加算器というものを作ります。これも並行して頑張ろうと思います。

加算器
モジュロ加算器

全体概要を把握する

パーツはコツコツ作っていてそれは頑張れば大丈夫そうです。最終的にできる回路はモジュロ指数という回路ぽいのですが、それをつかってそもそもどのように量子コンピュータで素因数分解ができるのかを把握してみたいと思います。

最終的に求めたいのはこれらしい。。。

3*5=15で考える

上記回路をつくればなぜ素因数分解ができるか全くわかってませんので、調べてみます。

$$x^r \equiv 1 mod n$$

となる最小のrを求めるようです。xは0からn-1までのnと互いに素なランダムな整数です。

参考:http://www-imai.is.s.u-tokyo.ac.jp/~imai/lecture/Shor.pdf

まず、15と互いに素な整数は、{1,2,4,7,8,11,13,14}のようです。

二つの整数 a, b が互いに素(たがいにそ、英: coprime, co-prime, relatively prime, mutually prime)であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。

https://ja.wikipedia.org/wiki/%E4%BA%92%E3%81%84%E3%81%AB%E7%B4%A0

かなり意味わかりませんが適当にやってみます。多分こういう値のxとrを使うと多分素因数分解できます。ちょっと考えたらこうじゃないかと思いました。

$1/15 = 0..1$

$2/15 = 0..2 , 2^2 =4$なので、$4/15 = 0…4$,$2^3 =8$なので、$8/15 = 0…8$,$2^4 = 16$なので$16/15 = 1…1$

$4/15 = 0…4,4^2/15 = 1…1$

$7/15 = 0…7$,$7^2/15 = 3…4$,$7^3/15=22…13$,$7^4/15 = 160…1$

というようにやっていると、何乗すれば15で割ったあまりが1になるか計算します。その結果、参考資料によると、

位数1:1

位数2 : 4,11,14

位数4 : 2,7,8,13

となるようです。

これは、4を2乗して15を引くとあまりが1になるというような感じで位数がきまります。ここまではなんとなくイメージできましたが、こっからが最後の仕上げのようです。

イメージとしては、例えば位数4の時の7をとりあげると、

$$7^{4/2}-1 \equiv 3 mod 15$$

48/15 = 3…3

$$7^{4/2}+1 \equiv 5 mod 15$$

50/15 = 3…5

なので、答えは3と5のようです。

正直よくわかりませんでしたが、もうちょっと数学的にきちんと理解しないといけなさそうでしたので次回に続きます。。。とにかく位数が見つかれば、あとは素因数分解はできるようでした。つづく

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方