導(dǎo)讀：

以后如果你看到量子計算機的新聞，千萬不要問“計算能力跟我的電腦比起來怎么樣”或者“打游戲會卡嗎”，人家一聽就知道你很外行。如果你問“它針對的是哪個數(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ù)分解”。有些科普文章把量子計算機描寫成無所不能，快成神了，這是重大的誤解。量子計算機的強大，是與問題相關(guān)的，只針對特定的問題。

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

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

量子信息究竟能用來干什么呢？下面我們來介紹量子信息的四項應(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)難。

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

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

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

這樣的計算量是什么概念？如果計算機一秒做1012次運算，那么分解一個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)典計算機上運行的，“最快的算法都無法破解RSA”指的是經(jīng)典計算機。對于量子計算機，我們卻已經(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)它還是非常困難的，造出有實用價值的量子計算機還需要很多努力。

第一次真正用量子算法分解質(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)狀?；疖噭偝霈F(xiàn)的時候，跑得沒有馬車快，還經(jīng)常出故障。但是任何有洞察力的人都能看出，火車代表著未來，因為它能夠達(dá)到的上限遠(yuǎn)遠(yuǎn)超過馬車。RSA現(xiàn)在當(dāng)然還可以用，但達(dá)摩克利斯之劍已經(jīng)懸掛起來了，任何有責(zé)任心的密碼人員都會時刻關(guān)心量子計算的進(jìn)展。

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

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

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

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

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

（未完待續(xù)）

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