淺談量子計算機-4 

4.2 多伊奇算法

上節介紹的Grover搜索算法，並不是第一個量子算法。第一個量子算法是由多伊奇發表的，多伊奇被譽為“量子計算之父”，是一位常人眼中行為奇特的科學家。

戴維·多伊奇教授是出生在以色列長在英國的猶太人，表面上，他是英國物理學家，牛津大學教授，量子計算先驅！不過他不教書，實際上是一個沒有固定工作的自由學者。他靠着演講、獎金和出書來賺錢為生，據說是位很少與人來往的牛津隱居者。

特別引起公眾矚目的，是多伊奇那兩本可以當作科普來讀卻又與一般科普完全不一樣的書：《真實世界的脈絡》和《無窮的開始》。書中多伊奇有許多新奇深奧的科學哲學觀點，在此我們不詳談，對他的書感興趣的讀者可閱讀參考文獻^【7，8】。

圖4.7：多伊奇

總而言之，多伊奇這位兩耳不聞窗外事的古怪科學家，在1985年突然聲名大振，因為他發表了一篇里程碑式的論文，文中他展示了Deutsch算法，表明量子計算可以比經典更快。7年後（1992年）發表了對多伊奇算法的推廣^【9】。在多伊奇算法啟發下的之後兩年間，量子算法來到多產期。Simon、Shor和 Grover的算法都在這期間相繼發表。

多伊奇算法沒有什麼應用，但作為第一個量子算法意義重大，它只適用於一種特殊的情況。因此作一個簡要介紹。

考慮一個只有一個變量的函數，輸入為0或1，輸出也為0或1。這樣的函數共有四個，分別記為f0、f1、f2和f3：函數f0，輸入0和1，輸出都是0，即f0(0) =0和f0(1) =0。函數f1，輸出與輸入相等，即f1(0) =0和f1(1) =1。函數f2，輸出與輸入相反，即f2(0) =1和f2(1) =0。函數f3，輸入0和1，輸出都是1，即f3(0) =1和f3(1) =1，見圖4.7下圖。

圖4.8：多伊奇函數

我們將函數f0和f3稱為常值函數，即對於兩個輸入，輸出都是相同的值的函數。如果一個函數一半的輸出是0，另一半的輸出是1，那麼就稱這個函數為平衡函數。例如f1和f2就是平衡函數（圖4.7上圖）。

Deutsch提出的問題是：隨機給定這四個函數中的一個，我們需要查詢多少次，才能確定這個函數是常值函數還是平衡函數？就是說我們不關心給定函數是四個函數中的哪一個，只問它是常值函數還是平衡函數。

首先想想經典計算需要多少次？經典計算機一次只能有一個輸入，也只能計算並輸出一個函數值。但是，為了回答多伊奇問題，我們必須把0和1都代入函數，所以一定需要做兩次經典操作。那麼，如果使用量子計算機呢？量子計算機優於經典計算之處，是因為量子比特是疊加態，它可以同時儲存1和0兩個數。那麼，就有可能操縱量子比特，同時對0和1進行計算，因此便有可能一次得出答案。實際上也可以做到，這正是多伊奇算法所展示的。

具體可用IBM模擬實例慢慢體會，在這兒首先直覺地理解一下，為什麼量子計算可以一次做到？

從多伊奇4個函數的定義出發，考慮另一個相關的“二進制和”函數Fi = (fi(0) + fi(1))。我們發現：F0 = 0、F1 = 1、F2 = 1、F3 = 0。也就是說，二進制和函數Fi有這樣的規律：對常值函數為0，對平衡函數，和值為1。

多伊奇的問題只是判定函數類型，是常值函數還是平衡函數？這是一種更為整體的性質，並不需要知道是fi中的哪一個。因此我們可以利用量子比特的疊加性，檢查二進制和Fi = (fi(0) + fi(1)) 是0還是1？這樣就能夠1次作出判定，Fi是常值函數還是平衡函數。

圖4.9：多伊奇算法

圖4.10：實現多伊奇算法的量子電路

圖4.9是多伊奇算法的解釋，圖4.10是實現多伊奇算法的具體量子電路。

實現多伊奇算法的電路，看起來簡單，輸入輸出皆為2。包括一個Oracle函數門、X非門、H門、最後測量。只測量第一個Qubit，第二個不需要測量。

測量後便能1次判定fi的性質（如結果1，是平衡函數；結果0，是常值函數）。

再解釋一下Oracle U(Fi)的作用。如果兩個量子比特寫成|x>|y>， Oracle U(Fi) 設計成這樣：第一個Qubit |x>不變，第二個Qubit |y>變成|y+f(x)>。f(x)就是多伊奇定義的那4個函數。所以Oracle門的輸出與f(x) 有關。

多伊奇算法的量子電路圖中有t0到t4，共5個時間點，初始態|00>，通過X非門，變|01>。然後，|+>|->，再經過Oracle Uf。用相位Oracle的公式，第2個量子比特保持|->不變，測量第1個量子比特，如果結果為0，是常值函數；結果為1，是平衡函數。所以經典計算機要作2次，而用多伊奇算法的量子計算只用1次。

圖4.11：多伊奇-喬薩算法

多伊奇-喬薩算法想法是類似的，第一個比特推廣到n個量子比特。測量前n 個量子位，如果測得|00 … 0態的話，說明f (x)是常數函數；如果測得的狀態不是|00…0態時，說明f(x)是對稱函數。 

相對於經典算法的2ⁿ +1次計算，量子算法只需一次黑盒計算，實現了相對的指數加速。

4.3 秀爾算法-1（經典，數論部分）

最重要的量子算法是秀爾（Short）算法，假如有了可用的量子計算機，我們便可以用它破解RSA加密算法。RSA是保障銀行安全常用的加密解密方法，它的基礎是因數分解問題。加密過程中將兩個互素數p和q相乘得到N = p*q。加密是作一次乘法就完成的簡單操作，但是反過來的解碼過程則非常困難。

RSA算法的解碼過程需要將一個整數N 作“質因數分解” ，得到質數p和q使得N = p*q。對經典計算機，時間複雜度是指數級別。例如，要分解d個十進制數字的整數N，蠻力算法需要遍歷所有素數p直到sqrt(N），檢查是否p能整除N。分解 d=230的N需要10²⁵次運算。2021年最快的計算機每秒鐘1200萬億次（1.2x10¹⁵ /s，也得運算2000年左右。

圖4.12：秀爾算法和經典算法

然而，秀爾量子算法展示了：在量子計算機上，因數分解問題可以在N的多項式時間內被有效解決，即足夠大的量子計算機可以破解RSA，見圖4.12。IBM於2001年成功展示秀爾算法實例，使用7個量子比特的量子計算機，將15分解成3×5，之後又分解21=3x7。這兩個數字都很小，但卻表明了秀爾算法具體實現的可能性。

秀爾的整個算法，分為經典算法和量子算法兩部分。經典部分完成可以在多項式時間內能用經典算法完成的計算，而將最困難的“傅里葉變換估算周期”，留給量子算法解決。如果用經典算法來“估算周期”，最好的情況也仍然是以指數增長。最有效的經典因式分解算法，稱為通用數域篩選法，可實現d^1/3（N=10^d）運行時間指數。

概括秀爾量子算法：1，經典，因式分解化為周期查找問題；2，量子，傅里葉變換估算周期。首先介紹經典部分：將分解因子化為周期查找問題？這個“周期”是怎麼回事呢？

20 世紀 70 年代，數學家們就知道，如果可以找到一個模指數函數的周期，那麼因式分解大數N就會變得容易。模函數k(mod N)表示的是k除N ，即k/N，的餘數。例如，如下恆等式a ≡b(mod N) 的意思是說，整數a和b被N除的餘數相同。

我們用如下幾個實例來加深對模函數以及“模指數函數的周期”的理解。

例1：假設N=15和k=1，1(mod 15)=1，因為1/15餘數是1。進一步，將k代入其它正整數：2(mod 15)=2、  3(mod 15)=3、……。當k=15的時候，15(mod 15)=0；而當k=16的時候，16(mod 15)=1，再回到了模函數值為1的情況。顯而易見，除15餘數為1的不止1和16，還有很多：1、16、31、46、61……。也就是說，模函數k(mod 15)，對整數k一直寫下去的話，一定的周期後（15），數值會循環，寫出的序列是一個周期為15的周期函數：1，2，3，……，0，1，2，3，……。

不過這不是我們感興趣的周期函數，我們感興趣的是另外一種，叫做“指數” 模周期函數。

例2：仍然以N=15為例，但這次不用正整數序列，而用某一個整數的“指數”序列來模N，比如，用2的“冪指數”形成的序列：1，2，4，8，16，32，64，128，256 …

也就是序列：2⁰，2¹，2²，2³，2⁴，2⁵，2⁶，2⁷，2⁸ …        （1）

用2的“冪指數” 序列（1）模15之後，得到另一個序列：

1，2，4，8，1，2，4，8，1 …                     （2）

可以看出，這個序列 (2) 的周期是4，我們將其稱為 “指數a=2” 的模周期，用r表示。在這個例子中，N=15，a=2時，模周期r=4。除了2的“冪指數“序列外，也可以用其它整數a的冪指數序列，如以下例3所示。

例3：例如給定a=7， 然後，給定冪指數序列：1，7，7²，7³，7⁴，7⁵ …，用這個序列模 15之後，得到的序列是：

1，7，4，13，1，7……

這個序列的周期r正好也為4。

例4：對2的“冪指數”序列模 21後得到：1，2，4，8，16，11，1，2，4 …，周期r是6。

數論學家們發現這種“指數” 模周期r，對整數N的素因子分解大有用處！一旦得到了周期r，並且r是個偶數的話，N就可以被分解成兩個素數的乘積，為什麼呢？

周期r被定義為滿足a^r  ≡ 1(mod N)的最小正整數，另外我們又有1  ≡ 1(mod N)。將上面兩個式子相減可得：

 (a^r -1) ≡ 0(mod N)。                                      （3）

此外，如果r是偶數，(a^r -1) 可以因式分解為兩個因子的乘積：

(a^r -1) = (a^r/2 +1) (a^r/2 -1)。                             （4）

圖4.13：秀爾算法中經典部分

圖4.13總結了秀爾算法中經典部分的算法。根據公式(3)，(a^r -1) 是N的倍數，然而，因為周期r是滿足條件(3)的最小正整數，再與 (4)結合起來看，說明a^r/2-1和 a^r/2+1不是N的倍數，但它們的乘積(a^r -1)卻是N的倍數。

假設N可以分解為兩個素數因子p1、p2的乘積，即N=p1p2。上一段分析而得到的結論只在下麵條件下才能成立：，p1 、p2分別是a^r/2-1、 a^r/2+1的素因子。 因此，我們可以通過計算最大公約數： gcd(N, a^r/2-1) 及gcd(N, a^r/2+1)，來找到p1和p2 ，也就是將N分解。

可以用上面的例4進行具體計算來說明這個過程。例4中，N=21，a=2，r=6，周期r是滿足a^r  ≡ 1(mod N)的最小正整數，即2⁶  ≡ 1(mod 21)。因為r=6=3x2，是偶數。

可寫成8²  ≡ 1(mod 21)，此外我們又有：1²  ≡ 1(mod 21)；兩式相減得：(8²-1²)  ≡ 0 (mod 21)

或者：(8+1) x (8-1)  ≡ 0 (mod 21)。然後我們計算最大公約數：

GCD(21, 9)=3，GCD(21, 7)=7，所以，N（=21）可因式分解為：21=3x7。

這個例子可以推廣到一般情況，因此，只要找到了指數模周期r，便能將N分解成質因數p1、p2的乘積。然而如何尋找指數模周期r呢？這就要藉助於量子算法來加速計算。

圖4.14：秀爾算法總體流程圖

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

 （待續）

參考文獻：

【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

相關視頻：

（待續）

Contents

**** 1.  前言 ****

**** 2.  歷史 ****

**** 3.  基礎 ****

3.1 疊加態

3.2 量子比特

3.3 量子門

3.4 量子電路

**** 4.  算法 ****

4.1 Grover 量子搜索算法

4.2 多伊奇算法

4.3 秀爾算法-1（經典，數論部分）

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

**** 5.  實現 ****

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

作者部分YouTube視頻：

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

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

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