因數分解演算法、周期查找演算法（簡化）

2019 年 10 月 3 日
筆記

質因數分解的複雜是公認，這也是我們將他作為 RSA (一種廣泛使用的公鑰加密演算法)的數學難題的原因。

(N=P*Q) (P、Q是質數)，n = length of N in bit

對於這麼一個N，我們因數分解得到結果的時間複雜度是 (2^n) ，因為這個複雜，所以也有一堆的數學家在努力降低這個的時間複雜度，目前的優化結果的時間複雜度是 (2^{ sqrt[3]{n}}) 。

那麼量子是否能夠有更好的結果呢？

在講因數分解之前，需要先提周期查找演算法。

周期查找 Period Finding

周期查找的基礎是量子傅里葉變換。

Input :

(f:(0,1,2,…,M-1) rightarrow S) for all x (f(x)=f(x+r))

challenge ：

find r

condition:

1) f is 1-1 on period 在周期內，f是一個一一對應的函數

2）(M>>r) (M>2r^2)

3）M能夠被r整除（這是一個簡化條件，稍後會有不簡化的怎麼辦）

這個電路，我的輸入是 $ frac{1}{sqrt M} sum_{x=0}^{M-1} |xrangle |0rangle$

經過f(x)後，我的量子疊加態是 $ frac{1}{sqrt M} sum_{x=0}^{M-1} |xrangle |f(x)rangle$

此時，如果測量了下面的 f(x)，那麼上面的量子態會坍縮，會變成只有f(x)等於測量結果的x，顯而易見，這是一個周期函數。

在量子傅里葉變換中，我們提到過傅里葉變換的第一個特點，當輸入shift了，結果是不會變的。

如果我們輸入的量子態的概率幅為 (alpha_0 , alpha_1, alpha_2, alpha_3,…, alpha_{N-1}) ，輸出的量子態的概率幅為 (beta_0 , beta_1, beta_2, beta_3,…, beta_{N-1})

則，當我們將輸入的概率幅變為：(alpha_{N-},alpha_0 , alpha_1, alpha_2, …, alpha_{N-2}) 輸出的概率不變。(這裡寫得是概率，不是概率幅，概率是概率幅的平方)

也就是說，我測量的隨機結果可能是這個周期當中的i個值，我也能shift成在第一個位置。

即，把 [0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 ……] (每個周期五個，第三個為1，其餘為0) 變成 [ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 …… ] (每個周期五個，第三個為1，其餘為0) 。

他們經過傅里葉變換後的結果是一樣的。

其實到這裡，我們發現，我們測不測量f(x)其實都沒有關係，因為在這前面所有測量結果對應的x，都是同一個周期的周期函數，因為shift的原因，他們傅里葉變換後的結果都是一樣的。

那麼，這麼做的意義是？

量子傅里葉變換還有第二個特點：傅里葉變換可以改變周期函數的周期。

他可以把周期為r的函數，變成周期為 (frac{M}{r}) 的函數。

對最後的這個函數測量，得到的結果是 (frac{M}{r}) 的倍數，多測量幾次就知道了 (frac{M}{r}) 的值。知道了這個值，很容易反推出r的值，周期查找完成。

如果沒有簡化條件呢？

即，M不是r的倍數。

那，假設測量結果為L，則找到一個最接近 (frac{L}{M}) 的分數 (frac{t}{r}) ，唯一的要求是 (M>2r^2) 最後通過一種叫做continued fraction的方法找到r。

因數分解

一個例子：

問題：找N=21的因數。

解法：

step 1:

(2^0=1 (mod 21)) 除以21後餘數為1

(2^1=2 (mod 21))

(2^2=4 (mod 21))

(2^3=8 (mod 21))

(2^4=16 (mod 21))

(2^5=11 (mod 21))

(2^6=1 (mod 21))

step 2:

(2^6-2^0=0 (mod 21))

(2^6-1=0 (mod 21))

((2^3-1)(2^3+1)=0 (mod 21))

到這一步，我們發現了什麼？

((2^3-1)(2^3+1))是21的倍數，那麼他的兩個因數 ((2^3-1)) 和 ((2^3+1)) 一定和21有公約數。

gcd(21,7)=7

gcd(21,9)=3

gcd求最大公約數大家還熟悉嗎？

比如說，我們相找21和15的最大公約數。

(21=15*1+6)

(15=6*2+3)

(6=3*2+0)

最大公約數就是最後一個不為0的餘數，這裡就是3。求最大公約數的演算法很快，大概是在 (log N) 的級別。

那麼現在的問題其實就是step1 ，找到函數 (f(a)=x^a mod N) 的周期，在上述例子中 (2^0) 和 (2^6) 取余相等，這就是一個周期，周期為6.

現在因數分解問題就全部轉化為了周期查找問題。

而周期查找問題恰好，有量子加速的方法，前文已經提過了，不再累述，我們知道周期查找有一個前提條件是 (M> 2r^2) ，在這個例子中，我們不知道r是多少，這個是我們要求的，但是我們知道，r<N，所以直接讓 (M > 2N^2) 就好。

變成電路圖就是：

得到周期，然後經過 step 2 就是我們想要的因數分解。

參考資料：
Quantume Mechanics & Quantume Computation Lecture 10