09 - Shor 演算法 (Shor's Algorithm) [Factor]

Shor 演算法:量子的因式分解演算法

目前,以解 RSA 為例,只能透過一些特性 (ee 太小、太大、重複使用 … ),來用不同的方法找,這邊先不提。

還沒有一個可以通用,來解所有質因數分解的問題

Shor 演算法也因此威脅到許多現有的加密方法。

因式分解

說到因式分解,如果有一個數字,我們要如何做到因式分解呢?

一個一個找,找到 (N)\sqrt(N) … 痾, … 行,但是不優 XD"

先把問題作簡化:

假設有一個數 1<x<N1<x<N

可以使 x21 mod Nx^2\equiv 1\ mod\ Nx±1 mod Nx \neq \pm 1 \ mod \ N

N(x21)\Rightarrow N|(x^2-1)

因為 NN 可以整除 (x21)=(x1)(x+1)(x^2-1) = (x-1)(x+1)

又因為 1<x<N1<x<N,故 (x1)(x-1)(x+1)(x+1) 必有一個與 NN 有公因數。

於是我們隨便找一個 x (1<x<N)x\ (1<x<N),但是不太可能亂找就找到 x21 mod Nx^2\equiv 1\ mod\ N

好在最大公因數 gcd(x,N)=1gcd(x,N)=1,代表存在有一個 RR 可以使得 xR1 mod Nx^R \equiv 1\ mod\ N

假設找到了這個 RR ,剛好 RR 為偶數,那麼 (XR2)21 mod N(X^\frac{R}{2})^2 \equiv 1\ mod\ N 就成功了。

簡而言之,我們可以透過以下的步驟找到 RR

  1. 選擇任意整數 xx1<x<N1<x<N (NN 則為需要被我們分解的數)
  2. f(k)=xk mod Nf(k) = x^k\ mod \ N 必為週期函數,而這個週期 : RR
  3. 如果 RR 不為偶數,重來
  4. 如果 f(R2)=1f(\frac{R}{2}) = -1 重來
  5. 反之 gcd(f(R2+1,N)gcd(f(\frac{R}{2}+1,N) , gcd(f(R21,N)gcd(f(\frac{R}{2}-1,N) 即為質因數。

Shor’s Algorithm

一般來說,要找到這個 RR 並不容易,傳統電腦只能透過爆搜一個一個找

我們的目標是透過量子電腦,找出這個週期 RR

怎麼找呢?! EX: N=15,x=7N=15,x=7

檢查 gcd(x,N)gcd(x,N) 不為 11 -> 解

開始 Order Search (一個一個找) [量子的優勢XD]:

f(x)=xk mod Nf(x) = x^k\ mod \ N

準備兩組 0|0\rangle 通過 HtH^{\otimes t}

Ht001nk=0n1k0=1n(0+1+2+....+n1)0H^{\otimes t}|0\rangle|0\rangle \Rightarrow \frac{1}{\sqrt{n}}\sum^{n-1}_{k=0}|k\rangle|0\rangle = \frac{1}{\sqrt{n}}(|0\rangle+|1\rangle+|2\rangle+ .... +|n-1\rangle)|0\rangle

後方的 0|0\ranglef(x)f(x) 做 XOR 0f(x)f(x)\Rightarrow |0\oplus f(x)\rangle \rightarrow |f(x)\rangle 得到 1nk=0n1kf(x)\frac{1}{\sqrt{n}}\sum^{n-1}_{k=0}|k\rangle|f(x)\rangle:

1N(070 mod 15+171 mod 15+...(n1)7(n1) mod 15)\frac{1}{\sqrt{N}}(|0\rangle|7^0 \ mod\ 15\rangle + |1\rangle|7^1 \ mod\ 15\rangle + ... |(n-1)\rangle|7^{(n-1)} \ mod\ 15\rangle)

1N(01+17+24+313+41+57+64+713+.....)\frac{1}{\sqrt{N}}( |0\rangle|1\rangle + |1\rangle|7\rangle + |2\rangle|4\rangle + |3\rangle|13\rangle + |4\rangle|1\rangle + |5\rangle|7\rangle + |6\rangle|4\rangle + |7\rangle|13\rangle + ..... )

稍微整理一下:

=1N((0+4+8+...)1= \frac{1}{\sqrt{N}}( (|0\rangle + |4\rangle + |8\rangle + ...)|1\rangle

+(1+5+9+...)7+ (|1\rangle + |5\rangle + |9\rangle + ...)|7\rangle

+(2+6+10+...)4+ (|2\rangle + |6\rangle + |10\rangle + ... )|4\rangle

+(3+7+11+...)13+ (|3\rangle + |7\rangle + |11\rangle + ... )|13\rangle

對第一組 qubits 做 “反傅立葉轉換(ZnZ_{n})” 會變成 …我知道很複雜,所以寫在後面,哈哈,這邊先假設 (n=16)(n=16) 的話:

=1N((0+4+8+...)1= \frac{1}{\sqrt{N}}( (|0\rangle + |4\rangle + |8\rangle + ...)|1\rangle

+(0+i48i...)7+ (|0\rangle + i|4\rangle -|8\rangle -i ...)|7\rangle

+(04+8...)4+ (|0\rangle - |4\rangle + |8\rangle - ...)|4\rangle

+(0i48+i...)13+ (|0\rangle - i|4\rangle -|8\rangle +i ...)|13\rangle

對第一個組 qubit 作測量,拿到 0,4,8,120,4,8,12 的機率各 14\frac{1}{4}

隨後我們可以計算出

sr=measuren=016,416,816,1216=0,14,12,34\frac{s}{r} = \frac{measure}{n} = \frac{0}{16},\frac{4}{16},\frac{8}{16},\frac{12}{16} = 0,\frac{1}{4},\frac{1}{2},\frac{3}{4}

上面的例子,有一半的機率可以找到 r = 4 (剛好又是偶數)

f(42)=f(2)=4f(\frac{4}{2}) = f(2) = 4

找到 1515 的質因數為: (41),(4+1)(4-1),(4+1)

code :
Shor’s Algorithm

Reference :





這邊是反傅立葉轉換發生的事 … 不想看者請跳www

j1Nk=0n1wjkk,(w=e2πin)|j\rangle \rightarrow \frac{1}{\sqrt{N}}\sum^{n-1}_{k=0}w^{jk}|k\rangle, (w=e^{\frac{-2\pi i}{n}})

把第一組拿去做傅立葉轉換:

得到 : kαkk\Rightarrow \sum_{k}\alpha_{k}|k\rangle : αk=4N1N(w2k+w6k+w10k+...)\alpha_k = \sqrt{\frac{4}{N}}\cdot\sqrt{\frac{1}{N}}(w^{2k}+w^{6k}+w^{10k}+...)

注意到 j=2,6,10,...2(2m+1)w2ijkπn=w2i2(2m+1)kπnj = 2,6,10, ... 2(2m+1) \rightarrow w^{\frac{-2ijk\pi}{n}} = w^{\frac{-2i2(2m+1)k\pi}{n}}

我們找 n=16,k=4n=16,k=4 : w=w2i2(2m+1)4π16=wi(2m+1)π=wiπ=1w=w^{\frac{-2i2(2m+1)4\pi}{16}}=w^{-i(2m+1)\pi}=w^{-i\pi} = -1

… 未完待續