4.4 秀爾算法-2（量子部分）

上面介紹的量子秀爾算法的經典部分，解釋了它將一個大整數分解為兩個素數因子的過程，即就是將其轉化成了周期查找問題的過程。周期查找問題對經典而言關鍵而困難，對此問題經典算法的複雜度是指數級別，而秀爾用量子計算機可將複雜度降到多項式級別。

秀爾算法中只有“周期查找”這一步，是需要在量子計算機上完成的，其他都可在經典計算機上完成。量子計算機運行完“計算周期”的子程序後，就會將結果，即周期r，返回給經典計算機，讓它繼續完成計算過程。

實際上，量子計算和經典計算各有利弊。量子比特的特點是疊加態，有可能被利用來實現並行計算而加快算法，但是，在量子計算的過程中一般不進行（或少進行）測量，因為測量伴隨着疊加態的塌縮，一旦塌縮到一個本徵態，便失去了量子計算的優勢，而經典計算有容易掌控的優越性。因此，專家們認為，量子計算機或許永遠不會單獨存在，而是一直和經典計算機配合執行任務，各展其長。輸出輸入以及複雜度簡單的部分由經典計算完成，特殊問題的困難部分由量子計算完成，就像秀爾算法這樣，便是用經典與量子配合起來完成破解RSA密鑰的過程。此外，與許多量子算法一樣， Shor算法是概率性的。也就是說，它以高概率給出正確答案，並且通過算法的重複來降低失敗的概率。

秀爾量子算法的周期查找，由指數模操作和量子傅里葉變換兩部分組成，如圖4.15a所示Shor算法依賴於模運算和量子並行計算，下面介紹秀爾算法中量子部分（圖4.15b），看看秀爾算法是如何找到周期的？

圖4.15：秀爾算法-量子

描述周期函數最合適的數學方法，是傅里葉變換Fourier Transform。秀爾周期查找的核心技術，正是被稱為量子傅里葉變換的QFT。

首先看一下我們問題中的周期函數長什麼樣？這是來自於數論得到的一個重要結果：設F(a) 等於x的a次方mod N，那麼F(a)是一個周期函數。

用上一節4.3中的例3為例，即N=15、x=7，我們得到序列：

7⁰(mod 15) = 1,  7¹(mod 15) = 7,  7²(mod 15) = 4,  7³(mod 15) = 13,  7⁴(mod 15) = 1……等等。

這個例子的周期函數F(a)如圖4.15c所示。秀爾算法量子部分的目的是要找到指數模序列F(a)的周期，可歸納為下列過程，我們在介紹一般過程時，也將上述例子結合於對過程的解釋中：

首先，選擇一個等於2的冪的整數q，定義它的取值範圍為N^2≤q≤2N^2。例子中的N=15，我們選取q=256；再選擇一個與N互質的隨機整數x ，我們選取x等於7。

第二步，創建一個量子寄存器R，將其劃分為兩個獨立的寄存器：R1和R2，R1用作輸入寄存器，R2輸出。R1必須有足夠的個量子位來表示任何q-1以內的整數；R2必須有足夠的個量子位，來表示任何N-1以內的整數。對例子中的具體數值，R的12個量子比特分成兩部分，n=8和m=4。

如圖4.15b所示，用y0、y1、y2、y3分別代表4個不同時間點的量子態。將R1和R2初始化為全0時的狀態為y0。然後，對R1的量子位應用哈達瑪變換，即應用n個H門到n個基態0，這將使寄存器R1的組合狀態成為從0到q-1的（2的n次方個）均勻等權的量子疊加態，而R2不變，總狀態記為y1。

再次強調一下：哈達瑪德H門很重要，能產生量子疊加態。一個H門作用後產生兩個基態的疊加，n個H門則產生2的n次方個基態的疊加。不過，在這兒的秀爾算法中，產生的不僅僅是R1的均勻疊加態，而且必須使得R1和R2互相糾纏，也就是使輸入和輸出互相糾纏。這樣，當我們測量一個使其塌縮時，也影響到另一個狀態的塌縮。

從y1到y2的轉換，是應用一個特別的量子轉換門（黑箱Oracle），使指數模函數f(a)=x^a(mod N)生效，生成指數模周期序列。即將量子態|a> |0>映射成|a> |x^a (mod N)>。對上述具體例子，轉換門之前和之後的量子態y1和y2的表達式如圖4.16所示。 

圖4.16：量子黑箱函數的作用

換言之，量子黑箱函數的作用是：為存儲在寄存器R1中的每個數計算x^a模N，並將計算結果存儲在寄存器R2中。由於量子並行性，x^a模N的計算可以在量子計算機上一步完成。這個步驟完成之後，量子存儲寄存器的聯合狀態為y2。我們將y2按輸入輸出展開後，再根據輸出寄存器重新排列：

圖4.17：y2的重新排列

雖然輸出寄存器R2有4個量子位，可以表示0-15之間的任何數，但因為例3中的模周期函數7^a(mod 15) 只有4個數值：1、7、4、13，所以y2中的R2是|1> 、|7>、|4>、|13> 的均勻疊加態。

然後對輸出量子位R2進行測量。這時 有趣的事情發生了：測量輸出R2使其以相同的概率塌縮成4個態中的一個。例如塌縮成|1> ，因為R2和R1互相糾纏，所以R2的塌縮也造成了R1的部分塌縮。

圖4.18：測量R2造成自己塌縮以及R1的部分塌縮

因此，測量後的合成態如圖4.18所示：y(2-3)的輸出部分只有一項，y(2-3)的輸入部分仍然是疊加態，也是一個周期序列，正等待作QFT。

最後，執行量子傅立葉變換求周期。QFT算法很複雜難以詳細介紹，但傅里葉變換的概念是通用的。例如 如果輸入是正弦或餘弦函數，變換後的結果是在 某一頻率的德爾塔函數。對一般的周期函數 結果會是周期附近的多個尖峰。

在我們的具體例子中，峰值在0、64、128等。根據多次測量，不難計算出周期，我們例子中的周期r=4 。然後，便遵循上一講描述的程序，可以成功地分解N而得到N=5x3。

秀爾算法幾乎利用了量子計算機的所有優勢：一是疊加性，即量子位的多重表示。就是用哈達瑪達門製造出均勻疊加，疊加態可以同時進行平行運算，但卻不能測量。因為一旦測量，便會塌縮到所有本徵態的其中之一。因此，最好的辦法是將量子算法部分“包”在經典部分的中間，例如秀爾的量子部分包括QFT在內。從經典部分給量子部分輸入少量的參數，量子給經典返回周期的數值。而將大量計算量，利用量子比特的平行運算能力，在量子計算機內部完成。量子計算部分被包住了，不測量就不會塌縮！然而，秀爾也巧妙地利用了量子態之間的糾纏性，引起部分塌縮但仍然保持疊加態。另外，量子傅里葉變換利用了量子相乾性，因為物理中干涉衍射，其數學本質就是傅里葉變換。

如何用量子模擬線路實現秀爾算法？請參考IBM模擬軟件平台的文件^【10】。

 （待續）

參考文獻：

【1】Keynote talk, 1st conference on Physics and Computation, MIT, 1981。(International Journal of Theoretical Physics, 21: 467–488, 1982)

【2】Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等譯. 第1章 算法在計算機中的作用. 算法導論 原書第3版. 北京: 機械工業出版社. 2013年1月

【3】張天蓉. 世紀幽靈-走近量子糾纏（第二版）[M].合肥：中國科技大學出版社，2020年5月。

【4】Bloch Sphere（wikipedia），https://en.wikipedia.org/wiki/Bloch_sphere

【5】IBM Quantum (2022). estimator primitive (Version x.y.z) [computer software]. https://quantum-computing.ibm.com/

【6】Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212

【7】無窮的開始: 世界進步的本源，作者:戴維·多伊奇 (David Deutsch), 王艷紅, 張

出版社：人民郵電出版社，出版日期：2014-11-01

【8】真實世界的脈絡，作者: [英] 戴維·多伊奇，出版社: 廣西師範大學出版社，譯者: 梁焰 / 黃雄，出版年: 2002-8

【9】David Deutsch & Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A. 439 (1907): 553–558.

【10】Shor’s algorithm from IBM：

https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm

（待續）

********************************************************** 

作者部分YouTube視頻：

https://www.youtube.com/watch?v=0I8FdazqAvc&list=PL6YHSDB0mjBKB2LBZDKL9UhcMMx6GtOsx

https://www.youtube.com/watch?v=_d0wquZkOYU&list=PL6YHSDB0mjBJ6qgfin-xKmP3FtTQr4x7i

*********************************************************