導(dǎo)讀：

以后如果你看到量子計算機(jī)的新聞，千萬不要問“計算能力跟我的電腦比起來怎么樣”或者“打游戲會卡嗎”，人家一聽就知道你很外行。如果你問“它針對的是哪個數(shù)學(xué)問題，把計算量從什么改進(jìn)到了什么”，人家就知道你是懂行的了?！话闳宋也桓嬖V他！

前文參見： 

你完全可以理解量子信息（1） | 袁嵐峰

你完全可以理解量子信息（2-3） | 袁嵐峰

你完全可以理解量子信息（4-5） | 袁嵐峰）

你完全可以理解量子信息（6） | 袁嵐峰）

你完全可以理解量子信息（7） | 袁嵐峰

八、量子信息的優(yōu)勢

從以上內(nèi)容可以看出，量子信息跟經(jīng)典信息相比有很大的優(yōu)勢。

首先是一個顯而易見的優(yōu)勢。前面比喻過：經(jīng)典比特是“開關(guān)”，只有開和關(guān)兩個狀態(tài)，而量子比特是“旋鈕”，有無窮多個狀態(tài)。旋鈕的信息量顯然比開關(guān)大得多。

還有一個稍微復(fù)雜一點的優(yōu)勢。一個包含n個經(jīng)典比特的體系，總共有2^n個狀態(tài)。想知道一個函數(shù)在這個n比特體系上的效果，需要對這2^n個狀態(tài)都計算一遍，總共要2^n次操作。當(dāng)n很大的時候，2^n是一個巨大的數(shù)字。指數(shù)增長是一種極快的增長，比n的任何多項式都快。比如說，2^n比n的10000次方增長得還要快。

對n個量子比特的體系，卻有一個巧妙的辦法。使每個量子比特都處于自己的|+> =(|0> + |1>)/√2態(tài)，那么整個體系的狀態(tài)就是|++…+> = (|00…0>+ |00…1> + … + |11…1>) /2^(n/2)。（根據(jù)定義就可以知道，這是個直積態(tài)，不是糾纏態(tài)，雖然它確實是一個疊加態(tài)。糾纏態(tài)和疊加態(tài)是兩個概念。）仔細(xì)看看你會發(fā)現(xiàn)，0和1的所有長度為n的組合都出現(xiàn)在其中，總共有2^n項，剛好對應(yīng)n個經(jīng)典比特的2^n個狀態(tài)。對這個疊加態(tài)做一次操作，得到的就是所有2^n個結(jié)果的疊加態(tài)。量子比特的一次操作，就達(dá)到了經(jīng)典比特2n次操作的效果！

但在歡呼之前，我們需要認(rèn)清，這個巨大的優(yōu)勢并不容易利用。因為所有2n個結(jié)果是疊加在一起的，讀取出來需要做測量，而一做測量就只剩下一個結(jié)果，其余的結(jié)果都被破壞了。所以我們只能把這個優(yōu)勢稱為潛在的巨大優(yōu)勢，真要利用它，需要非常巧妙的算法。

這樣的算法只對少數(shù)的問題能夠設(shè)計出來，后面會舉一些例子，如“因數(shù)分解”。有些科普文章把量子計算機(jī)描寫成無所不能，快成神了，這是重大的誤解。量子計算機(jī)的強(qiáng)大，是與問題相關(guān)的，只針對特定的問題。

九、量子信息的應(yīng)用

前面說過，量子信息的研究內(nèi)容包括量子通信和量子計算。從這兩個名字我們立刻就可以發(fā)現(xiàn)，量子信息還沒有進(jìn)入生活，因為大家都還在用經(jīng)典的電腦和手機(jī)呢。具體地說，量子通信已經(jīng)有了一些實際應(yīng)用，量子衛(wèi)星就是做相關(guān)實驗的。而量子計算的發(fā)展程度要低得多，還處于演示階段，尚未造出有實用價值的量子計算機(jī)。

量子信息究竟能用來干什么呢？下面我們來介紹量子信息的四項應(yīng)用。在量子計算方面，有量子因數(shù)分解（破解最常用的密碼體系）和量子搜索（用途最廣泛的量子算法）。在量子通信方面，有量子隱形傳態(tài)（“傳送術(shù)”，最富有科幻色彩的應(yīng)用）和量子密碼術(shù)。在所有這些應(yīng)用中，量子密碼術(shù)是目前唯一接近實用的，但這一個就非常重要，足以表現(xiàn)量子信息的價值了。

十、量子因數(shù)分解和密碼破解

所謂因數(shù)分解，就是把一個合數(shù)分解成質(zhì)因數(shù)的乘積，例如21 = 3 × 7。因數(shù)分解是數(shù)學(xué)中的經(jīng)典難題。

你也許會問，這有什么難的？你當(dāng)然不管三七二十一就能分解21，但請試試看分解2^67 - 1 =147,573,952,589,676,412,927。這是個18位數(shù)。1644年（明朝滅亡的那一年），法國數(shù)學(xué)家梅森（Marin Mersenne）提出它是一個質(zhì)數(shù)。在那之后的很長時間里，人們都這么認(rèn)為。直到1903年（清朝都快亡了），人們才發(fā)現(xiàn)它是一個合數(shù)，等于193,707,721 ×761,838,257,287。耗了一個朝代！

讓我們想想，如何分解一個數(shù)字N。最容易想到的算法，是從2開始往上，一個一個地試驗?zāi)芊裾齆，一直到N的平方根為止。如果N用二進(jìn)制表示是個n位數(shù)，即N約等于2n，那么嘗試的次數(shù)大致就是2n/2。這是指數(shù)增長的計算量，前面說過，指數(shù)增長是一個災(zāi)難。

在計算機(jī)科學(xué)中，把計算量指數(shù)增長的問題稱為“不可計算的”，把計算量多項式增長的問題稱為“可計算的”。不可計算的意思并不是計算機(jī)不能算，而是計算量增長得太快，很容易就達(dá)到“把全世界的計算機(jī)集中起來算幾十億年都無法得出結(jié)果”的程度。

當(dāng)然，計算量是跟算法有關(guān)的，你可以尋找效率更高的算法，也應(yīng)該這么做。對于因數(shù)分解，“從2開始一個一個試”并不是最聰明的算法。在經(jīng)典計算機(jī)的框架中，目前最好的算法叫做“數(shù)域篩”，計算量有所減少，但仍然是指數(shù)增長。

“艾數(shù)學(xué)”同學(xué)，你想問數(shù)域篩的計算量具體是多少？一般人我不告訴他，答案是exp[O(n^(1/3) log^(2/3)n)]（在數(shù)學(xué)中，大寫字母O后面跟一個式子，表示結(jié)果跟這個式子具有同樣的數(shù)量級）。

這樣的計算量是什么概念？如果計算機(jī)一秒做1012次運(yùn)算，那么分解一個300位的數(shù)字需要15萬年，分解一個5000位的數(shù)字需要……50億年！地球的年齡也不過是46億年而已！

由此可以看出因數(shù)分解的一個特點：它的逆操作，即算出兩個質(zhì)數(shù)的乘積，是非常容易的；而它本身，卻是非常困難的。這種“易守難攻”的特性，使它在密碼學(xué)中得到了重要的應(yīng)用。

密碼學(xué)的基本框架，我們會在后面介紹量子密碼術(shù)時闡述。在這里，我們只需要指出一點：因數(shù)分解的困難性，是現(xiàn)在世界上最常用的密碼系統(tǒng)“RSA”的基礎(chǔ)。RSA這個名字，是三位發(fā)明者李維斯特（Ron Rivest）、薩莫爾（Adi Shamir）和阿德曼（Leonard Adleman）的首字母縮寫。

RSA是一種“公開密鑰密碼體系”，它的密鑰（即加密時用到的參數(shù)）是對全世界所有人公開的。為什么敢公開？因為這個密鑰是一個很大的合數(shù)，解密需要把它分解成兩個質(zhì)數(shù)，而發(fā)布者有信心別人在正常的時間內(nèi)解不開。

但是RSA有兩大隱患。第一點，我們只是知道目前公開的最好的算法是數(shù)域篩，但不知道是否有更好的算法。更令人寢食不安的是，某些國家、某些組織也許已經(jīng)掌握解密的算法了，只是沒有告訴你！

第二點，上面說的算法都是在經(jīng)典計算機(jī)上運(yùn)行的，“最快的算法都無法破解RSA”指的是經(jīng)典計算機(jī)。對于量子計算機(jī)，我們卻已經(jīng)知道了它可以破解RSA。

如前所述，量子計算相對于經(jīng)典計算有潛在的巨大優(yōu)勢，只是實現(xiàn)這種優(yōu)勢需要聰明的算法設(shè)計，只有對少數(shù)問題能夠設(shè)計出這樣的算法。而因數(shù)分解，就是這樣的問題之一。1994年，肖爾（Peter Shor）發(fā)明了一種量子算法，把因數(shù)分解的計算量減少到了多項式級別，也就是從不可計算變成了可計算。

艾數(shù)學(xué)同學(xué)，你又在舉手了？嗯，肖爾算法的計算量是O(n^2 logn loglogn)，一般人我不告訴他。

這又是個什么概念呢？同樣還是分解300位和5000位的數(shù)字，量子算法會把所需時間從15萬年減到不足1秒鐘，從50億年減到2分鐘！對RSA密碼系統(tǒng)來說，這不是“隱”患，而是“明”患！

看起來，全世界的密碼人員都應(yīng)該陷入恐慌了。但事實上還沒有，人們?nèi)匀辉谟弥鳵SA。為什么呢？因數(shù)分解的量子算法只是理論，真要實現(xiàn)它還是非常困難的，造出有實用價值的量子計算機(jī)還需要很多努力。

第一次真正用量子算法分解質(zhì)因數(shù)是在2007年實現(xiàn)的，把15分解成3 × 5。有兩個研究組同時做出了這個實驗，一個是中國科學(xué)技術(shù)大學(xué)的潘建偉和陸朝陽等人，一個是澳大利亞布里斯班大學(xué)的A. G. White和B. P. Lanyon等人。此后各國科學(xué)家不斷努力，把這個領(lǐng)域推向前進(jìn)。目前在實驗上分解的最大的數(shù)是291,311 = 523 × 557，是由中國科學(xué)技術(shù)大學(xué)的杜江峰和彭新華等人在2017年實現(xiàn)的。

什么，你前邊跟我說量子算法隨隨便便就能分解幾千位的數(shù)字，結(jié)果實際上最大只能分解一個六位數(shù)？你是在耍我嗎？

這位同學(xué)，請你先把手里的刀放下……同學(xué)們，一定要分清潛力和現(xiàn)狀。火車剛出現(xiàn)的時候，跑得沒有馬車快，還經(jīng)常出故障。但是任何有洞察力的人都能看出，火車代表著未來，因為它能夠達(dá)到的上限遠(yuǎn)遠(yuǎn)超過馬車。RSA現(xiàn)在當(dāng)然還可以用，但達(dá)摩克利斯之劍已經(jīng)懸掛起來了，任何有責(zé)任心的密碼人員都會時刻關(guān)心量子計算的進(jìn)展。

還有一點值得注意的是，造出專門處理某些任務(wù)的“專用”的量子計算機(jī)比造出“通用”的量子計算機(jī)要容易得多。專用的東西比通用的容易造，這是一個普遍規(guī)律。在可編程的電子計算機(jī)出現(xiàn)之前300多年，岡特（Edmund Gunter, 1581-1626）和奧特雷德（William Oughtred, 1574-1660）就造出了計算尺。

谷歌宣布計劃在2017年造出超越傳統(tǒng)計算機(jī)的量子計算機(jī)，很可能指的就是這種專用計算機(jī)。斯諾登從美國出逃后，披露了美國國家安全局有一個絕密的項目“穿透硬目標(biāo)”（Penetrating Hard Targets），計劃建造一臺專用于破解密碼的量子計算機(jī)。據(jù)傳該局已經(jīng)存放了大量外國政府的密電，一旦項目成功立刻對它們動手。這足以讓其他國家不寒而栗了！

同樣的道理，2017年5月，中國科學(xué)技術(shù)大學(xué)潘建偉和陸朝陽等人宣布造出世界上第一臺超越早期電子計算機(jī)的光量子計算機(jī)，也是特別針對一個問題的，這個問題叫做“玻色子取樣”。對它的量子算法，也是把指數(shù)增長的計算量縮減到了多項式增長的計算量。成果就是，這臺量子計算機(jī)算起玻色子取樣來，比第一臺電子管計算機(jī)ENIAC和第一臺晶體管TRADIC快了10到100倍。

順便提一下，有些人迷惑光量子計算機(jī)跟量子計算機(jī)是什么關(guān)系，甚至還有人說光量子計算機(jī)不是量子計算機(jī)。實際上，量子計算機(jī)總需要用某種物理體系來實現(xiàn)，好比電子計算機(jī)可以用電子管實現(xiàn)，也可以用晶體管實現(xiàn)，甚至可以像《三體》中設(shè)想的那樣用幾千萬人來實現(xiàn)（秦始皇：有人叫我？）。光量子計算機(jī)就是用光子作為量子比特的量子計算機(jī)。除了光子之外，量子計算機(jī)常用的物理體系還包括光學(xué)共振腔、離子阱、核磁共振等等。沒關(guān)系，你不需要現(xiàn)在就看懂這些物理學(xué)術(shù)語……

以后如果你看到量子計算機(jī)的新聞，千萬不要問“計算能力跟我的電腦比起來怎么樣”或者“打游戲會卡嗎”，人家一聽就知道你很外行。如果你問“它針對的是哪個數(shù)學(xué)問題，把計算量從什么改進(jìn)到了什么”，人家就知道你是懂行的了?！话闳宋也桓嬖V他！

（未完待續(xù)）

背景簡介：本文作者為袁嵐峰，中國科學(xué)技術(shù)大學(xué)化學(xué)博士，中國科學(xué)技術(shù)大學(xué)合肥微尺度物質(zhì)科學(xué)國家實驗室副研究員，科技與戰(zhàn)略風(fēng)云學(xué)會會長。