最近有一個(gè)新聞：中國(guó)科學(xué)技術(shù)大學(xué)潘建偉團(tuán)隊(duì)與中科院上海微系統(tǒng)所、國(guó)家并行計(jì)算機(jī)工程技術(shù)研究中心合作，成功構(gòu)建76個(gè)光子的量子計(jì)算原型機(jī)——九章，求解高斯玻色取樣只需200秒，而這個(gè)結(jié)果用當(dāng)今的超級(jí)計(jì)算機(jī)——太湖之光計(jì)算，卻需要20多億年。

有小朋友問：九章計(jì)算機(jī)真的這么快嗎？玻色采樣問題是什么？九章這么厲害，能不能破解我們的銀行密碼呢？今天我們就來討論一下九章的話題。

注意

要理解九章原理，我們必須理解許多數(shù)學(xué)概念。本文絕大多數(shù)內(nèi)容都在討論數(shù)學(xué)概念，中間過程對(duì)大多數(shù)讀者并不友好，可能會(huì)感覺到晦澀難懂，直到最后才會(huì)有畫龍點(diǎn)睛的一筆。本文針對(duì)新生事物進(jìn)行解說和揣測(cè)，有不同意見可以留言，謝絕杠精。

1??高爾頓釘板

為了討論量子計(jì)算機(jī)九章的原理，我們首先從以前討論過的一個(gè)話題：高爾頓釘板說起。

在街頭，你是否見過這樣的抽獎(jiǎng)游戲：把一個(gè)小球扔到一個(gè)布滿釘子的盒子里，小球經(jīng)過許多次與釘子的碰撞，最后掉到某個(gè)槽里，根據(jù)小球掉的位置，會(huì)給你相應(yīng)的獎(jiǎng)品。

這個(gè)裝置最早是由19世紀(jì)的英國(guó)學(xué)者高爾頓發(fā)明的，所以叫做高爾頓釘板。你會(huì)計(jì)算小球落在不同槽中的概率嗎？

我們以4行釘板為例：如果小球要掉入最左側(cè)或者最右側(cè)的槽中，它必須一路順著左邊或者一路順著右邊運(yùn)動(dòng)，小球落入最左側(cè)或者最右側(cè)槽的方法數(shù)都只有1種。

但是，如果小球要運(yùn)動(dòng)到A的位置，就有兩種方式了：要么從A的左上方向右到達(dá)A處，要么從A的右上方向左到達(dá)A處。所以，到達(dá)A處的路徑數(shù)等于A左上和右上兩個(gè)位置的路徑數(shù)之和。A=1+1=2。

按照這個(gè)規(guī)律我們就能寫出小球到達(dá)任意一個(gè)位置的方法數(shù)：等于它左上和右上兩個(gè)肩膀上的數(shù)字之和。

大家看：小球到達(dá)各個(gè)位置的方法數(shù)，構(gòu)成了一個(gè)楊輝三角（正如我們之前討論過的）。而且，每次撞擊釘板之后，小球向左和向右運(yùn)動(dòng)的概率都是1/2，因此所有的路徑都是等可能的。到達(dá)某個(gè)槽的方法數(shù)越多，概率就越大。

在4行釘板時(shí)，落入槽中的方法總數(shù)有1+4+6+4+1=16種。其中落入中央槽的方法數(shù)有6種，概率就是6/16=37.5%；落入第2、4兩個(gè)槽的概率是4/16=25%，而落到第1、5兩個(gè)槽的概率就是1/16=6.25%。

不過，如果槽的數(shù)量增加，我們還能計(jì)算出這個(gè)概率嗎？

我們來考慮一個(gè)問題：假如一共有n排釘子，對(duì)應(yīng)了n+1個(gè)槽，落入第k個(gè)槽的概率有多大？根據(jù)數(shù)學(xué)計(jì)算，這個(gè)概率的表達(dá)式如下：

?我們可以簡(jiǎn)單解釋一下這個(gè)公式，不過如果數(shù)學(xué)不太好，也可跳過這一段，這并不影響理解本文。

因?yàn)橛衝排釘子，小球每次撞擊釘子有2種選擇，所以最終小球的路徑方法數(shù)有2n種。如果想要落入第k個(gè)槽，那么在n次與釘子的撞擊中，需要有k-1次落到釘子右側(cè)，n-k+1次落到釘子左側(cè)。因此我們從n次碰撞中選擇出k-1次向右運(yùn)動(dòng)，方法就是組合數(shù)

種。用落入該槽的方法數(shù)，除以一共的方法數(shù)，就得到了概率。

仔細(xì)觀察這個(gè)表達(dá)式，我們會(huì)發(fā)現(xiàn)：假如要計(jì)算n=100時(shí)落入各個(gè)槽的概率，就需要計(jì)算到100的階乘，即

這么大的數(shù)字，計(jì)算起來特別復(fù)雜。有沒有什么更好的計(jì)算方法呢？

有，這就是采樣法！我們可以實(shí)際做一個(gè)實(shí)驗(yàn)，讓小球一次又一次落下，這就叫做采樣。然后，觀察每個(gè)球落入哪個(gè)槽中，并進(jìn)行統(tǒng)計(jì)，最后根據(jù)各個(gè)槽中小球的頻率分布，直接得到小球落入各個(gè)槽的概率。只要我們采樣的次數(shù)足夠多，根據(jù)大數(shù)定律，我們就能以足夠高的精度獲得這個(gè)概率。

不僅如此，如果我們已經(jīng)通過實(shí)驗(yàn)得到了小球落入各個(gè)槽的概率，再利用公式（1），就能反向計(jì)算出不好算的那個(gè)組合數(shù)了！計(jì)算需要很久的時(shí)間，我們通過采樣實(shí)驗(yàn)很快就完成了。

總結(jié)來講：我們做了一個(gè)物理實(shí)驗(yàn)，通過實(shí)驗(yàn)得到概率，再反過來計(jì)算出了一個(gè)復(fù)雜的數(shù)學(xué)問題。這種方法在歷史上經(jīng)常會(huì)被用到。比如著名的蒲豐投針實(shí)驗(yàn)（我們以前也介紹過），就是通過反復(fù)扔一根針，得到了圓周率的結(jié)果。

其實(shí)，量子原型機(jī)“九章“的玻色采樣過程與此類似。通過一套量子裝置，得到了一個(gè)概率結(jié)果，這個(gè)概率結(jié)果如果用經(jīng)典計(jì)算機(jī)計(jì)算非常復(fù)雜，但是用量子裝置卻可以立刻得到結(jié)果。

2? ?行列式

九章到底計(jì)算了一個(gè)什么問題呢？我們要從大學(xué)一年級(jí)時(shí)，我們學(xué)習(xí)過的線性代數(shù)上的一個(gè)概念——行列式說起。

把一些數(shù)字排列成一個(gè)mxn的矩形，我們稱之為一個(gè)矩陣。對(duì)于一個(gè)2x2的矩陣，我們可以求出它的行列式：

我們可以用這樣的方法記憶：右下的紅線連接的兩個(gè)數(shù)字相乘，減去左下的藍(lán)線連接的兩個(gè)數(shù)字相乘。

其實(shí)，行列式的計(jì)算在數(shù)學(xué)和物理上還是挺有用的。例如：兩個(gè)平面向量X=(a,c)和Y=(b,d)，以它們?yōu)榕R邊構(gòu)成了一個(gè)平行四邊形，它的面積S=ad-bc，實(shí)際上就是一個(gè)矩陣的行列式。

三階行列式的算法與之類似，只是項(xiàng)數(shù)更多：

同樣，我們可以用圖表示出來：紅色線連接的數(shù)字相乘再相加，藍(lán)色線鏈接的數(shù)字相乘再相減。

三階行列式可以用來計(jì)算一個(gè)平行六面體的體積——只需要把每個(gè)向量的三維坐標(biāo)組成一個(gè)3x3的矩陣，計(jì)算它的行列式就可以了。

在物理上，計(jì)算安培力和動(dòng)生電動(dòng)勢(shì)時(shí)，可以使用行列式的算法。

四階以上的行列式又該如何計(jì)算呢？我們有一個(gè)普遍表達(dá)式：

?Det(A)表示矩陣A的行列式，П表示連乘，sgn表示符號(hào)，在某些情況下是正的，另外一些情況下是負(fù)的。S?表示n個(gè)元素的置換群，也就是將1、2、3…n這些元素進(jìn)行全排列。公式大體意思是:將一些元素a_(i,σ(i))連乘，更換順序后再連乘...然后再把它們做加法或者減法，就可以得到行列式。

行列式有很大的用處，而且，行列式有很多很好的性質(zhì)，使得它可以找到更好的算法，降低計(jì)算復(fù)雜度。根據(jù)數(shù)學(xué)家們的計(jì)算，n階行列式計(jì)算復(fù)雜度為O(log2(n))級(jí)別，也就是：

計(jì)算1萬(wàn)億階的矩陣的行列式，計(jì)算復(fù)雜度也在100多步驟。行列式真是個(gè)物美價(jià)廉的好東西。

3? 積和式

不過，行列式的親兄弟——積和式就不這么友善了。它和行列式長(zhǎng)得很像，只是行列式有加也有減，積和式全都是加。

例如：二階積和式

N階積和式

對(duì)比行列式的表達(dá)式（2），我們會(huì)發(fā)現(xiàn)它們都是對(duì)角標(biāo)輪換后相乘再相加。只不過行列式有一個(gè)符號(hào)函數(shù)，有時(shí)取正有時(shí)取負(fù)，而積和式把所有的負(fù)號(hào)都去掉，變成了完全相加。

盡管只有這么一點(diǎn)點(diǎn)差別，但是積和式卻沒有行列式那么好的性質(zhì)，計(jì)算復(fù)雜度非常高。按照目前最優(yōu)的算法，n階積和式的計(jì)算復(fù)雜度是O(nx2?), 隨著n的增大，復(fù)雜度指數(shù)級(jí)上升。

例如，若有100階矩陣的積和式，計(jì)算復(fù)雜度大約1032，用當(dāng)今中國(guó)最快的超級(jí)計(jì)算機(jī)——太湖之光計(jì)算（每秒1017次）大約需要4000萬(wàn)年。

算法已經(jīng)沒法優(yōu)化了，我們還有什么辦法來計(jì)算積和式嗎？正如剛才，在高爾頓釘板問題上，我們?nèi)绻麤]辦法直接計(jì)算組合數(shù)，為什么不做個(gè)物理實(shí)驗(yàn)?zāi)兀?/p>

這種方法最早在伽利略時(shí)代就有應(yīng)用：伽利略在計(jì)算擺線下方面積時(shí)，用一個(gè)圓形鐵片在同樣厚度的鐵板上滾動(dòng)，畫出了一條擺線。用剪刀沿?cái)[線剪下鐵片，發(fā)現(xiàn)它的質(zhì)量是圓形鐵片的三倍，于是得到了這個(gè)面積是3πr2,后來，人們才用微積分證明了這個(gè)結(jié)論。

為了計(jì)算積和式，我們需要的物理實(shí)驗(yàn)就是玻色采樣問題。

4??玻色采樣問題

微觀粒子分為玻色子和費(fèi)米子，它們最大的區(qū)別是是否滿足泡利不相容原理。光子就是玻色子，它不滿足泡利不相容原理，兩個(gè)光子可以處于完全相同的狀態(tài)，我們稱為全通同粒子。而電子就是費(fèi)米子，兩個(gè)電子不能處于全部相同的狀態(tài)。

在量子力學(xué)中有一個(gè)基本問題：求解粒子的波函數(shù)φ，它表示不同粒子出現(xiàn)在不同位置的概率。如果有n個(gè)粒子，它們就會(huì)相互影響，它們的分布概率又怎么描述呢？此時(shí)我們就需要整體波函數(shù)，它描述了每一種粒子在每一個(gè)狀態(tài)或者位置的概率分布，它等于（簡(jiǎn)化寫法）

它的意思是：將每一個(gè)粒子波函數(shù)進(jìn)行排列（P），相乘后再相加。這是因?yàn)檫@些粒子是全同粒子，可以交換位置，把所有可能的情況都考慮到，再把它們相加，就代表了各種情況下粒子分布的概率了，這就是整體波函數(shù)。

這種先排列，再相乘，再相加的問題，大家是否感覺似曾相識(shí)？這不就是積和式（3）嘛！終于，2010年，麻省理工學(xué)院的教授阿倫森和他的博士生阿爾希波夫一起證明了一個(gè)結(jié)論：玻色采樣問題中粒子占據(jù)數(shù)分布概率正比于積和式的模方。

這句話很難理解，我們?cè)俅騻€(gè)比方。玻色采樣問題的實(shí)驗(yàn)裝置就好像有一個(gè)光子的高爾頓釘板，它的釘子是分束器，它的小球是光子。

光子進(jìn)入這個(gè)裝之后，會(huì)形成整體波函數(shù)，最終光子從哪個(gè)出口出來并不一定，但是卻有一定的概率分布?，F(xiàn)在給定光子從輸入端中的某些位置如進(jìn)入，求從某些口輸出的概率大小。阿倫森就是證明了，這個(gè)概率情況與一個(gè)矩陣的和積式的模方有關(guān)。

具體來講，這個(gè)概率是

其中S表示一種輸出情況，P(S)就是這種情況的概率，s1s2…表示此時(shí)各個(gè)能級(jí)的量子數(shù)，A就是與這套干涉裝置對(duì)應(yīng)的矩陣。

如果我們能夠通過采樣，計(jì)算出這個(gè)概率P，就能通過這個(gè)公式反推出積和式Perm(A)。我們知道，如果用經(jīng)典計(jì)算機(jī)，計(jì)算積和式是非常困難的。潘建偉團(tuán)隊(duì)的“九章“正是這樣一套實(shí)驗(yàn)裝置。

潘建偉團(tuán)隊(duì)利用更好的光源、干涉裝置和光子探測(cè)器，獲得了76個(gè)光子的輸出結(jié)果。在200秒內(nèi)采樣了數(shù)千次，完成了玻色采樣過程，得到了各種情況下的概率。這個(gè)概率如果使用經(jīng)典計(jì)算機(jī)太湖之光計(jì)算，大約需要20多億年，主要問題是因?yàn)榉e和式的計(jì)算過于復(fù)雜。

不過，九章只能算是一個(gè)原型機(jī)，而不是計(jì)算機(jī)。因?yàn)樗褂昧孔拥姆椒ㄈツM量子過程，速度當(dāng)然會(huì)超過經(jīng)典計(jì)算機(jī)。這就好像點(diǎn)燃一個(gè)爆竹問碎片怎么飛，物理方法1秒就知道了，可是用計(jì)算機(jī)去計(jì)算可能要知道爆竹的結(jié)構(gòu)、火藥的種類，甚至要知道每一個(gè)分子和原子的位置，要獲得足夠的精度，計(jì)算量非常大。這并不是因?yàn)榻?jīng)典計(jì)算機(jī)不行，而是因?yàn)槭澜缣珡?fù)雜。

不過，經(jīng)典計(jì)算機(jī)的優(yōu)勢(shì)在于通用性，既可以算爆竹爆炸，也能算炮彈的軌跡?？墒蔷耪履壳爸荒芴幚聿Ｉ蓸訂栴}，或者可以計(jì)算和積式。而且，任意給一個(gè)和積式，能否轉(zhuǎn)化成相應(yīng)的光路也未可知。對(duì)于更多其他的問題，例如證明量子計(jì)算機(jī)優(yōu)越性的大數(shù)的質(zhì)因數(shù)分解問題，九章更是無能為力。

所以，至少到目前為止，我們的銀行密碼還是安全的。即便有一天，人們真正造出了通用量子計(jì)算機(jī)，它也只能在某些方面優(yōu)于傳統(tǒng)計(jì)算機(jī)，許多的生活場(chǎng)景例如打電話、玩游戲，可能還是經(jīng)典計(jì)算機(jī)更有優(yōu)勢(shì)。量子霸權(quán)時(shí)代，還遠(yuǎn)遠(yuǎn)沒有到來。