量子算法分析：深入算法內核掌握量子計算的精髓

量子計算往往容易被媒體吹噓得神乎其神，寫這篇目的也是為了能夠讓更多的人了解量子計算的精髓和靈魂，同時也是我理解量子計算的一個過程，分享出來希望能夠給想要試圖理解量子計算的小伙伴一點啟示。

對于量子計算我也好些年沒搞了，目前的水平也只能如此了，如有錯誤，望各位海涵。由于論壇不支持公式編輯，因此文字中的公式只能用類似字母代替，推導的公式也只能截圖，如果閱讀時對應不上，可以留言。

一、前言

很多人對于量子計算或多或少都有所了解，但目前量子計算圈和安全圈存在著巨大的鴻溝，關于量子計算報道大多喜歡夸大其詞，讓人感覺量子計算像玄學一樣，徒增神秘感，并不利于量子計算思想的普及。很多人雖然對量子計算做了很深入了解，但大多事后仍舊疑惑不解：為什么量子疊加態還能參與計算？量子計算機又是怎樣實現并行運算的？量子計算機又是如何解決特定問題的？

本文就從量子計算最為重要的算法—Shor算法開始做詳細探討，看它是如何破解RSA的？為了更通俗易懂，本文涉及的公式推導都盡量詳細，力求高中水平的數學基礎能看懂。你既不需要懂密碼學，也不需要懂量子力學也能明白算法的精髓。

本文將詳細分析Shor算法的實現過程，整數周期數及非整數周期數下Shor算法分析，Shor算法概率評估，實例分析。不得不說，量子計算以及量子計算機是一個很龐大的知識體系，個人水平有限，此處我們僅僅就單純地圍繞Shor算法本身進行探討分析，不考慮退相干對算法的影響，也不考慮物理實現。

廢話不多說，先回答幾個讓人疑惑的問題。

1.為什么量子疊加態還能參與計算

一個量子可以同時處于兩種狀態的疊加（比如自旋向上和自旋向下），這種疊加態測量的瞬間就會隨機變為一個確定的態（測量得到自旋向上），這個過程叫波函數的坍塌。我們如果將這兩個態表示為0,1，而每種態觀測后出現的概率幅(注意不是概率，概率幅的平方為概率為1）為α,β，那么這個量子可以表示為：

這里右尖括號為狄拉克符號，表示量子態， 0,1為基態，+表示疊加，兩種態的概率幅平方和為1，即 α^2+β^2=1 。而我們通常說的量子計算就是通過量子邏輯門來操作處于疊加態的量子。比如Hadamard門，簡稱H門（在量子計算中非常重要），他的一個主要功能就是通過計算基態產生等概率的疊加態。通過H門變換后的單量子疊加態為：

兩種基態的坍塌概率都為1/2 ，兩個量子的H門得到的結果如下：

每個態坍塌的概率 1/4 ，對于n個量子的H門變換后：

其他量子門這里就不做介紹了，本文暫時不會涉及，想更深入了解可以到維基上看。

https://en.wikipedia.org/wiki/Quantum_logic_gate

量子門及其對應的門矩陣如下圖：

量子門及門矩陣，圖片來自wikipedia

還有一個比較重要的復合門是受控U(a,x)門，想深入了解的看這篇文章：一只冰牙喵：4.2 受控操作（https://zhuanlan.zhihu.com/p/422428222），不過這里看不懂也沒關系，我們只需要知道受控U門可以用于計算以a為基底的冪，其一般用于生成指數函數值。

受控U門（來自https://zhuanlan.zhihu.com/p/422428222）

2. 量子如何做并行運算

量子并行運算（Quantum Parallelism）是基于量子疊加態（Quantum Superposition）和幺正變換實現的。量子計算正是有了數據的可疊加性和幺正變換，從而決定了一次操作即可改變全部數據。

比如有量子寄存器，存了10個處于疊加態的量子，在通過運算時只需要一次性操作這10個量子，但是由于可疊加性，這10個量子疊加態可以表示2^10個基矢，一次操作10個量子，相當于一次對2^10個基矢進行了操作，這就大大提高了運算的速度。

在經典計算中，并行性的核心思想是將一個計算任務分配給多個處理器同時運行，要快于使用一個處理器來運行。在理想的情況下，將工作分配給K 個處理器就應該使計算時間縮短為原來的1/K。但是現實肯定不是這樣的，真實的任務往往具有串聯性，只有部分具有并聯性的子任務才能夠做并行運算。

由于量子計算的特點是數據的可疊加性質和操作的幺正變換本質，從而就決定了量子計算的語義特征是完全意義上的通過一次操作即可改變全部數據的并行計算。將一個N 位量子寄存器中的 2^N 個數據同時通過一次幺正變換（即進行一次運算）所需的時間定義為 Tq ，而經典計算中對一個數據進行運算的時間為 Tc ，因為一次量子計算就對所有的數據做了并行處理，所以量子計算加速能力可以表示為：

如果 Tc=Tq ,那么加速能力 S=2^N,也就是說對量子計算機做一次運算，相當于對經典計算機做 2^N 次運算。

此外，一臺量子計算機并不一定在所有計算任務上都比一臺經典計算機做得好，比如乘法運算在一臺量子計算機上執行就不如傳統計算機上快。為了突出量子計算機的優越性，就需要開發量子并行效應能力的算法。

3.量子計算能做什么

量子計算機是嚴重依賴于優秀的量子算法的實現，雖然通用量子計算機能做經典計算機的所有事情，但是只有在處理特定問題上量子計算才具有決定性的優勢，目前已經有很多優秀的量子算法，其中對大數因子分解，離散對數問題以及更一般的隱含子群問題的解決有著開創性和重大影響的量子算法便是本文要詳細分析的Shor算法。

本文將非常詳細的分析Shor算法來讓各位明白量子計算在解決特定問題上的巨大優勢。

二、Shor算法分析

在費曼提出量子計算機概念不到15年的時間，shor通過研究出的量子算法給世人了一劑強心針，自從shor算法出來后，人類開始加速了量子計算機的研制，各大頭部企業也紛紛加入了量子計算機的量子競賽行列。

shor算法最令人振奮的是直接將質因子分解以及離散對數問題以指數級速度提升，這給人們的啟示是可以利用同樣算法思想來解決更為廣泛的隱含子群問題。

我們知道RSA是基于經典計算機大數質因式分解的指數復雜度的困難而設計的一種非對稱加密算法，目前最優的因子分解算法為指數復雜度：

而通過shor量子算法可以以多項式復雜度完成大數因式分解，從而可以快速破解RSA算法。那么Shor算法是如何發揮如此威力的，簡單來說，Shor算法的核心依賴于三個變換即H變換,U變換,QFT(量子傅立葉)，接下來我們一步一步的分析。

Shor算法量子實現線路簡圖：

Shor算法量子實現線路圖

1、RSA算法

我們設RSA的公鑰為 (e,N) ，私鑰為 (d,N) ,那么生成公私鑰的過程如下：

1.生成兩個足夠大的素數p,q，得到合數N=p*q，然后計算得到p-1和q-1的最小公倍數L。

2.生成e,使得e和L互質，且滿足13.生成d，使得d*e%L=1且1

那么加密解密操作如下：

我們知道RSA是基于大數N的因子分解的困難而設計的非對稱加密算法，因此我們只要能夠實現大數N的因子分解，就可以破解RSA，這里不做證明了，網上有很多資料。這里你只需要知道，我們可以通過公私鑰的N，然后通過Shor算法求得N的因子p,q就可以了。

2、問題轉化

首先我們需要將大數因子分解問題轉化為以求待分解的合數N為模的函數 f(x)=a^x ( mod N) 的周期問題。

設周期函數f(x)=a^x（mod N）的周期為r（這里a為小于N，且與N互質的整數），則有：f(x)=f(x+r) , 那么：

設整數：

則：

那么 x-1， x+1 都能被 kN 整除，那么一定存在 gcd(x+1,N)>1 或者 gcd(x-1,N)>1 (gcd是一個用輾轉相除法求公因子的函數)，也就說與N存在一個大于1的公約數，這個公約數就是N的分解因子。

例如：設 N=15，a=7 ,則：

由此，我們只要求出f(x)的周期，就能輕而易舉的分解合數了。而shor算法的精髓就是利用量子特性來快速求解得到周期r.

3、通過Shor算法求周期r

設量子比特長度為 L, 則總共可以表示的 q=2^L 個基態, 設N為要分解的合數，為了確保 2^L 長度內有足夠的周期數，我們需要滿足：

然后，我們利用Hadamard門來構造等概率的量子疊加態 |x>存入寄存器reg1，然后利用U門來構造 |f(x)> 的疊加態存入寄存器reg2，且使這兩個寄存器處于糾纏態。

兩個寄存器展開形式如下：

由于 f(x) 為周期函數，設周期為r，A為總長2^L中存在的周期數，則：

設l為小于一個周期內的x的值, x=l+Ar, 則整個系統的態實際為：

因此，x可以表示為：

然后對reg2進行計算基上的測量，設測量結果設為 Z ，測量Z在reg1中的投影變化為：

例如 N=15，a=7 ，測量后的整個系統的態為：

經過投影后：

這里，當測量得到一個γ 值后，由于寄存器reg1和寄存器reg2是處于糾纏態，所以Z值測量后寄存器reg1會塌陷為相同Z值的|x>疊加態，如果reg2測量的值為1，那么reg1則處于 (|0>}+|4>}+|8>+...) 的疊加態，那么周期 r 的信息就包含在reg1中，因此對reg1進行量子傅里葉變化：

上式可以變換為：

這里為什么要這么變換，因為當測量Reg2時，Reg2坍塌為了r個值中的一個值，所以每一個值對應reg1中的A個疊加態。

這里設：

這里，我們需要考慮兩種情況，一種是 2^L 能夠整除 r 的情況，也就是在 2^L 內剛好有整數個周期，一種是不能整除的情況。如果能夠整除，那說明每個波峰剛好位于 ?=k2^L/r ，不能整除時，波峰位于非常接近波峰的兩側，因為波峰處的 ? 本應該為非整數，而我們測量得到 ?只能是整數，所以這時候我們需要加入微調的參數。接下來我們分別對這兩種情況進行分析。

A.整數周期

在(2)式的[ ]中，在 ? 是 2^L/r 的整數倍情況下變成，出現相長干涉，求和后為 A=2^L/r ，如果不為整數，則為相消干涉，其值趨于0。所以：

當 γ≠ k2^L/r 時，我們通過等比數列轉化得到：

帶入（0）式得：

由于：

也就是說，當γ≠ k2^L/r ，也即不為整數時，為相消干涉，其值為0。

通過量子傅里葉變換后得到如下疊加態：

測量|γ> 的值，等概率1/r地選擇出一個態。由

得：

如果有：

r 就可以從γ/2^L}的不可約分數求出。

B. 非整數周期

2^L 不能整除 r 的情況下,那么在x值范圍內的周期數A便不是整數，此時我們加入微調參數δk 稍作調整，使得γ為整數，設

因此(2)式的[ ]為：

這里 δk的值極小，該值用于逼近函數的峰值，我們再令：

因此(3)式的平方表示為：

由于：

因此：

所以得到 γ的概率為：

這里，為了嚴謹討論，我們設 |δk| 小于等于1/2（如果大于1/2，可以認為是下一個整數 z-(1-δ) ），所以這是適用于所有情況的：

由(4)(5)得：

當α∈[0,π/2]， sinα 必位于原點與點(π/2,1) 連線的上方，所以：

而對于任意 α ， |sinα| 為凸函數，有：

又因sin(θ/2)≤ θ/2 ,因此：

所以，測量|γ> 的概率為：

最后，我們來討論測量值γ，有：

所以：

這里 γ已測得，這里嚴格存在一個分數k/r,可由 γ/(2^L) 的連分數展開求出（下一個節將通過實例說明），通過約分滿足 gcd(k,r)=1 就可得到 r 的值，gcd算法的成功率為：

也就是說我們能以大于：

的概率分解N的因子再加上量子傅里葉變換的復雜度為 Ο(n^2) ,所以shor算法的時間復雜度為 Ο(n^2rlogr) 。

三、實例分析

雖然上面已經分析得很透徹了，但是估計還是有人覺得會太抽象，所以下面我以一個例子來進行實例分析，以幫助理解。

對于 f(x)=a^x(mod N) ，N=91，a=4，那么：

所以周期為 r=6， N<2^7 ,L=2x7=14，然后根據2，3式我們計算得到：

這里， γ 是我們測量得到值，如果這個值為0，那么對于我們求周期r是沒有意義的，所以除開這種情況下，測得其他值的概率和為0.623。如果測量的值為13653，那么我們來計算0.833312的連分數。

1/0.833312=1.200031,

1/0.200031=4.999225,

1/0.999225=1.000775,

1/0.000775=1290.322580

這里遇到大數1290，我們就終止，最后我們得到連分數為：

那么我們就可以確定 k=5,r=6 了嗎，那有沒可能 k=10,r=12 呢，所以，我們不能單純的通過一次測量來確定周期，我們來考察其他幾項，我這里不再一一去展開了，懶人可以在這里去計算(連分數計算 -連分數計算器-分數計算器)。

因此，如果我們將shor算法多執行幾次，最后求出各個分母的最小公倍數，那么這個最小公倍數就是我們要找的周期r，有了周期r，我們就不難求出合數N的質數因子了，進而也能夠比較容易破解RSA算法了。

四、離散對數問題簡析

通過對shor算法原理的剖析，我們可以知道，對于任何具備轉化為求周期函數的周期為目標的問題都可以用同樣算法以指數加速來快速解決，比如離散對數(ElGamal), ECC之類的非對稱加密算法都可以用同樣的思想來解決。

離散對數多說兩句，Shor在其原始論文中對于素域上的離散對數問題，給出了一個基于整數求階量子計算算法求解算法,成功率為1/480。Shor指出在解決素域上的離散對數問題時，其實并沒有利用到素域的特性，因而對有限域上的離散對數問題也同樣成立。后來Eicher和Opku給出了一個在多項式時間內以1/480的成功率攻擊橢圓曲線離散對數問題的量子計算算法。

設一個階為 p ,且生成器為g 的群 G（g∈G ）,如果 x=g^r(mod p)∈ G ,那么對于部分 r∈Ζp ,我們希望得到 r ,那么 r 就是離散對數：