量子計算 21 量子算法 6 Shor Part III: QFT+PF

• 1 周期尋找量子态
• 2 QFT矩陣
• 3 QFT解決周期尋找問題
• • 假如Q是s的整數倍
  • 假如Q不是s的整數倍

上回書介紹了QFT的量子電路，這其實是之前講的Shor算法裡面的第三步，我們今天來看第二步：

1. 第一步，把質數分解問題，轉化為周期尋找問題，這一步Shor認為是顯然的，當然我們不會這麼認為。。。
2. 第二步，通過量子傅裡葉變換QFT，以 O ( 1 ) O(1) O(1)查詢複雜度解決周期尋找問題
3. 第三步，建立QFT的量子電路，用 n O ( 1 ) = log ⁡ n O ( 1 ) n^{O(1)}=\log n^{O(1)} nO(1)=lognO(1)個量子門
4. 第四步，把冰箱門關上，用Continued Fraction Algorithm把QFT的輸出變成質數分解的結果，然後大象就裝冰箱裡了

1 周期尋找量子态

第二步就是在我們已經有了QFT之後，用QFT作用之後的測量結果如何能解決周期尋找問題(Period finding QF)

已知我們的第一步在量子計算19中已經得到了周期尋找問題的相關量子态：

∣ ψ ⟩ |\psi\rangle ∣ψ⟩的這些分量，本來是 ∣ 0101 …   ⟩ |0101\dots\rangle ∣0101…⟩形式的二進制，不過目前轉化成了整數來表達，有 q q q個qubit，整數的範圍也就是 0 ∼ ( 2 q − 1 ) = ( Q − 1 ) 0\sim (2^q-1)=(Q-1) 0∼(2q−1)=(Q−1)；從向量的形式來看，其分量 ∣ r ⟩ |r\rangle ∣r⟩也就是在第 r r r個位置上為1的機關向量。

2 QFT矩陣

我們的第三步已經在量子計算20中完成，即得到了QFT的快速量子電路，現在我們進行第二步，即将QFT作用于上述量子态。

QFT其實是以下矩陣 F Q F_Q FQ​:

F Q F_Q FQ​是個 Q × Q Q\times Q Q×Q的矩陣， Q = 2 q Q=2^q Q=2q， q q q是量子比特的數目； w i j = e 2 π i / Q w^{ij}=e^{2\pi i/Q} wij=e2πi/Q是機關1在複數範圍的Q次方根。

3 QFT解決周期尋找問題

是以第二步就是 F Q ∣ ψ ⟩ F_Q|\psi\rangle FQ​∣ψ⟩，根據上述分析，對于 ∣ ψ ⟩ |\psi\rangle ∣ψ⟩中的第 l l l個分量 ∣ r + l s ⟩ |r+ls\rangle ∣r+ls⟩， F Q ∣ r + l s ⟩ F_Q|r+ls\rangle FQ​∣r+ls⟩的結果相當于取矩陣 F Q F_Q FQ​的第 r + l s r+ls r+ls行，是以 F Q ∣ ψ ⟩ F_Q|\psi\rangle FQ​∣ψ⟩結果為：

第一個求和，代表的是 F Q F_Q FQ​的第 r + l s r+ls r+ls行共有 Q Q Q個分量；第二個求和，代表的是 ∣ ψ ⟩ |\psi\rangle ∣ψ⟩共有 l l l個分量。

然後我們研究的問題就是，對于某個 ∣ k ⟩ |k\rangle ∣k⟩，其幅值的相幹是constructive interference還是destructive interference，為此我們可以先忽略其中的global phase w r k w^{rk} wrk，因為對于特定的k是一樣的，于是我們來看：

假如Q是s的整數倍

我們知道 w i j = e 2 π i / Q w^{ij}=e^{2\pi i/Q} wij=e2πi/Q

當 k s ks ks不是Q的整數倍時，随着 l l l的增長， k s l m o d    Q ksl \mod Q kslmodQ會在 0 ∼ Q − 1 0\sim Q-1 0∼Q−1之間周期增長，反應到複數的機關圓上如下圖，是以 L L L個這些周期複數加起來大多數就互相抵消了，是以就産生了destructive interference。

那當 k s ks ks是Q的整數倍的時候， w k s l = 1 w^{ksl}=1 wksl=1，是以這樣的 ∣ k ⟩ |k\rangle ∣k⟩的幅值，在 l l l個求和之後，是發生了constructive interference的。

是以大機率上，我們觀測到的 ∣ k ⟩ |k\rangle ∣k⟩，對某整數 c c c，滿足 k s = c Q    ⟺    k = c Q s ks=cQ\iff k=c\frac{Q}{s} ks=cQ⟺k=csQ​，是以我們經過多次運作量子電路可以獲得多個： c 1 Q s , c 2 Q s , … c T Q s c_1\frac{Q}{s}, c_2\frac{Q}{s}, \dots c_T\frac{Q}{s} c1​sQ​,c2​sQ​,…cT​sQ​，是以計算他們的最大公約數，在T很小的情況下，就能很大機率上獲得我們想要的周期 s s s。

假如Q不是s的整數倍

假設對于量子态分量 ∣ k ⟩ |k\rangle ∣k⟩，有 k = c Q s + Δ k=c\frac{Q}{s}+\Delta k=csQ​+Δ，則當 Δ \Delta Δ越小，其被觀測的結果越大，接下來分析： ∑ l = 0 L − 1 w k s l = ∑ l = 0 L − 1 e 2 π i k s l / Q = ∑ l = 0 L − 1 e 2 π i ( c Q s + Δ ) s l / Q = ∑ l = 0 L − 1 e 2 π i Δ s l / Q \sum_{l=0}^{L-1}w^{ksl}=\sum_{l=0}^{L-1} e^{2\pi iksl/Q}=\sum_{l=0}^{L-1} e^{2\pi i(c\frac{Q}{s}+\Delta)sl/Q}=\sum_{l=0}^{L-1} e^{2\pi i \Delta sl/Q} ∑l=0L−1​wksl=∑l=0L−1​e2πiksl/Q=∑l=0L−1​e2πi(csQ​+Δ)sl/Q=∑l=0L−1​e2πiΔsl/Q

是以，當 Δ \Delta Δ很小的時候，當 l l l在 0 ∼ L − 1 0\sim L-1 0∼L−1變化時，在複數機關圓上的變化如圖，這種時候是方向相近的向量疊加，發生了constructive interference；

反之，當 Δ \Delta Δ較大時候，不同的向量方向差異較大，就會産生周期變化互相抵消，産生destructive interference，因為我們知道 L ≈ Q s L\approx \frac{Q}{s} L≈sQ​，是以 Δ \Delta Δ接近1的時候這些量子幅就相當于分布在機關圓周圍一圈了，如果再小上幾倍，比如小10倍，其實就變成了相當的constructive interference。

是以，很高機率上，我們觀察到的 k = c Q s + Δ k=c\frac{Q}{s}+\Delta k=csQ​+Δ，是非常接近某個整數 c Q s c\frac{Q}{s} csQ​的，其機率分布圖如下：

是以， k = c Q s + Δ    ⟺    k Q = c s + Δ Q    ⟺    ∣ k Q − c s ∣ = Δ Q k=c\frac{Q}{s}+\Delta\iff \frac{k}{Q}=\frac{c}{s}+\frac{\Delta}{Q}\iff |\frac{k}{Q}-\frac{c}{s}|=\frac{\Delta}{Q} k=csQ​+Δ⟺Qk​=sc​+QΔ​⟺∣Qk​−sc​∣=QΔ​，是以 ∣ k Q − c s ∣ = Δ Q |\frac{k}{Q}-\frac{c}{s}|=\frac{\Delta}{Q} ∣Qk​−sc​∣=QΔ​是很小的 ( ∼ 1 Q ) (\sim \frac{1}{Q}) (∼Q1​)，我們已知觀測到的 k k k和 q q q個qubit ( Q = 2 q Q=2^q Q=2q)，不知道的是 c c c和 s s s，僅僅知道他們都是整數，且 s < < Q s<<\sqrt{Q} s<<Q

​。

怎麼求解 c c c和 s s s呢？請見下回Continued Fractions!