量子計(jì)算機(jī)能否改變世界？

陳克非

（1 杭州師范大學(xué)理學(xué)院；2 衛(wèi)士通摩石實(shí)驗(yàn)室）

編者按：量子計(jì)算是一種利用量子特性的新型計(jì)算技術(shù)。目前，量子計(jì)算機(jī)的計(jì)算能力正在逐步提高，但受限于理論及技術(shù)問(wèn)題，目前距離建造出真正的通用量子計(jì)算機(jī)還較遙遠(yuǎn)。本文介紹了量子計(jì)算、量子算法及量子計(jì)算機(jī)的研究進(jìn)展，并對(duì)量子計(jì)算的未來(lái)進(jìn)行了展望。

1 量子計(jì)算機(jī)能否分解大整數(shù)？

去年夏天，在引人矚目的 2017 國(guó)際密碼大會(huì) (Crypto2017)上，加州大學(xué)圣巴巴拉分校約翰·馬提尼斯（John Martinis）教授的特邀報(bào)告“量子整數(shù)分解計(jì)算機(jī)展望（Prospects for a quantum factoring machine）”中介紹了他所領(lǐng)導(dǎo)的Google量子計(jì)算機(jī)團(tuán)隊(duì)的工作[圖1]，他坦承要真正做出穩(wěn)定實(shí)用高效的量子計(jì)算機(jī)還有很多的路要走，想要使用量子計(jì)算機(jī)破解現(xiàn)在主流采用的RSA 密碼，10年之內(nèi)幾乎不可能實(shí)現(xiàn)，因?yàn)橛刑嗟募夹g(shù)問(wèn)題需要解決， 在他看來(lái)這些真的很困難。

圖1.約翰·馬提尼斯教授在做“量子整數(shù)分解計(jì)算機(jī)展望”的特邀報(bào)告

經(jīng)典計(jì)算機(jī)，利用 1 和 0 來(lái)表示經(jīng)典物理量（如電流、電壓等）的有與無(wú)，因而 1 和 0 組成的比特（bit，信息量單位）就可用來(lái)存儲(chǔ)和處理信息。比特的值要么是 1，要么是 0。任何經(jīng)典信息都只不過(guò)是由“1”和“0” 組成的一個(gè)長(zhǎng)序列。

在量子力學(xué)中，光子偏振態(tài)、電子的自旋態(tài)、離子的能級(jí)、量子糾纏等物理量都具有兩個(gè)狀態(tài)。這兩個(gè)狀態(tài)可以編碼成量子比特（qubit）的 1 和 0， 但另一方面這些系統(tǒng)遵循量子疊加原理，一個(gè)量子位可以同時(shí)處于 1 狀態(tài)和0 狀態(tài)，即處于一種疊加狀態(tài)[圖2]。若用量子比特來(lái)存儲(chǔ)數(shù)據(jù)，由于量子特性，n個(gè)量子比特的存儲(chǔ)器可以存儲(chǔ)2n個(gè)數(shù)據(jù)，數(shù)據(jù)存儲(chǔ)能力隨著量子比特?cái)?shù)的增多而呈指數(shù)級(jí)增長(zhǎng)。

量子計(jì)算機(jī)利用量子特性來(lái)完成計(jì)算。由于量子疊加效應(yīng)，n比特的量子計(jì)算機(jī)可同時(shí)處于2n種狀態(tài)，當(dāng)量子計(jì)算終止時(shí)，2n種狀態(tài)因?yàn)闇y(cè)量而坍塌到一種確定的狀態(tài)，從而完成計(jì)算[1]。量子計(jì)算機(jī)的一次操作同時(shí)完成了對(duì)2n個(gè)數(shù)據(jù)的操作，相當(dāng)于經(jīng)典計(jì)算機(jī)完成了對(duì) 2n個(gè)數(shù)據(jù)的并行處理。所以說(shuō)，這種疊加性讓量子比特能夠比比特編碼處理多得多的信息，這就是量子計(jì)算機(jī)相對(duì)于經(jīng)典計(jì)算機(jī)的優(yōu)勢(shì)。

圖2.經(jīng)典比特與量子比特

量子疊加特性使得量子計(jì)算具有極強(qiáng)的并行處理能力，但另一方面，該特性也導(dǎo)致量子態(tài)的不穩(wěn)定和難以操控。很多人往往只注意到量子計(jì)算的空前競(jìng)爭(zhēng)是比誰(shuí)能夠操控更多量子比特?cái)?shù)，而實(shí)際情況是做到穩(wěn)定精確有效地操控量子比特，降低量子比特運(yùn)算過(guò)程中所產(chǎn)生的誤差，這可能是更難的。由于量子計(jì)算機(jī)錯(cuò)誤率高的問(wèn)題，一些科學(xué)家和數(shù)學(xué)家質(zhì)疑它們的實(shí)用性。谷歌和其他的公司稱該問(wèn)題可通過(guò)糾錯(cuò)算法來(lái)解決，但那些算法需要更多的量子比特來(lái)檢查進(jìn)行運(yùn)算的量子比特的工作。有的專家估計(jì)，檢查單個(gè)量子比特的工作將需要額外增加 100 個(gè)量子比特。

2 量子計(jì)算機(jī)研究進(jìn)展

上面提到量子力學(xué)原理是下一代計(jì)算革命的關(guān)鍵所在。在加州圣巴巴拉的一個(gè)小型實(shí)驗(yàn)室里，馬提尼斯領(lǐng)導(dǎo)的谷歌物理學(xué)家和工程師在利用量子力學(xué)來(lái)打造運(yùn)算潛力令人膛目結(jié)舌的計(jì)算機(jī)[圖3]。可靠的規(guī)?；孔佑?jì)算機(jī)有望改變從 AI 到化學(xué)的各行各業(yè)，加速機(jī)器學(xué)習(xí)的發(fā)展，帶來(lái)新型的材料、化學(xué)物和藥物。

2017年10月17日 Intel 公司發(fā)布了包含 17個(gè)量子位的超導(dǎo)測(cè)試芯片[圖4]，之前只有IBM公司推出相同規(guī)模量子計(jì)算芯片。同一天，IBM宣布量子計(jì)算已經(jīng)突破了49量子比特的障礙（Quantum computing—breaking through the 49 qubit simulation barrier）[圖5]， 在全球范圍量子計(jì)算機(jī)領(lǐng)域的公認(rèn)領(lǐng)跑者是IBM 和 Google。2017年4月份，Google 開(kāi)發(fā)出具有9 個(gè)量子位的計(jì)算芯片；2017年5月，IBM 展示了首個(gè)包含 17 個(gè)量子位的芯片。IBM 的成果基于耶魯大學(xué)教授羅伯特·施羅科夫（Robert Schoelkopf）的研究，而 IBM 的團(tuán)隊(duì)中也有他的多名博士生和研究生。Google 的工作則基于加州大學(xué)圣巴巴拉分校教授約翰·馬提尼斯（John Martinis）的研究，他的研究團(tuán)隊(duì)自 2014年獲得了谷歌的支持，并開(kāi)展合作研究。

圖3.Google 位于加州圣巴巴拉的實(shí)驗(yàn)室里，量子芯片被凍結(jié)在懸在空中的低溫恒溫器里

圖4.Intel 公司展示的 17 個(gè)量子位的超導(dǎo)測(cè)試芯片

2017年5月，中國(guó)科技大學(xué)研究團(tuán)隊(duì)宣布通過(guò)電控可編程的光量子線路構(gòu)建出可用于多光子“玻色取樣”任務(wù)的光量子計(jì)算模擬機(jī)。有人認(rèn)為中科大的工作應(yīng)該還屬于實(shí)驗(yàn)室里的原理機(jī)，還算不上通用的量子計(jì)算機(jī)。

目前，各大科技公司的研究員都在開(kāi)發(fā)包含50個(gè)量子位的芯片。這樣的芯片計(jì)算能力將超過(guò)當(dāng)前所有超級(jí)計(jì)算機(jī)。目前還不清楚， 在獲得如此強(qiáng)大的計(jì)算能力之后，我們可以做些什么，解決什么樣的問(wèn)題。不過(guò)，目前的挑戰(zhàn)主要是開(kāi)發(fā)規(guī)模更大的量子計(jì)算機(jī)。

圖5.IBM 公司宣布量子計(jì)算突破 49Qubit

Intel 研究人員表示，量子位極其脆弱， 任何噪聲或無(wú)意的干擾都會(huì)令量子位丟失數(shù)據(jù)。此外，量子位依靠超導(dǎo)體金屬，而這樣的超導(dǎo)體必須處于極低的溫度下。Intel 表示， 量子位的運(yùn)行溫度為“20 毫開(kāi)爾文”，比太空冷 250 倍，制造并維持這樣的環(huán)境難度很大。除了低溫之外，量子位的開(kāi)發(fā)還有其他問(wèn)題。隨著量子計(jì)算機(jī)的規(guī)模越來(lái)越大，可能發(fā)生的故障類(lèi)型也越來(lái)越多。

3 量子計(jì)算與量子算法

1936年，Alan Turing提出Turing機(jī)模型，通過(guò)機(jī)器來(lái)模擬人們的計(jì)算過(guò)程。該模型隱含的觀點(diǎn)是一臺(tái)裝有足夠資源的計(jì)算機(jī)能實(shí)現(xiàn)任何合理的算法。

1982年， Richard Feynman 發(fā)現(xiàn)在經(jīng)典計(jì)算機(jī)上難以模擬量子過(guò)程，該模擬過(guò)程需要超指數(shù)級(jí)的存儲(chǔ)空間和運(yùn)行時(shí)間，指出Turing機(jī)的功能也許并沒(méi)有人們所想的那么強(qiáng)大。Feynman提出將量子力學(xué)與經(jīng)典計(jì)算機(jī)結(jié)合起來(lái)，引入量子計(jì)算的概念。

關(guān)于量子計(jì)算，目前已經(jīng)取得了很多進(jìn)展，如開(kāi)發(fā)建造量子比特?cái)?shù)越來(lái)越大的芯片等，這使人們感覺(jué)似乎只要工程技術(shù)進(jìn)步就可以實(shí)現(xiàn)大型通用量子計(jì)算機(jī)的建造。然而，事實(shí)上關(guān)于量子計(jì)算機(jī)的基礎(chǔ)物理問(wèn)題并沒(méi)有得到完全解決，而這些與量子計(jì)算技術(shù)的實(shí)現(xiàn)緊密相關(guān)。

量子比特所能做的事情與電子比特所能做的事情并無(wú)本質(zhì)上的區(qū)別。只是由于量子特性，量子比特能夠同時(shí)處于兩種疊加狀態(tài)，且處于相干態(tài)的多個(gè)量子比特在執(zhí)行特定的計(jì)算任務(wù)時(shí)，一個(gè)量子比特的變化會(huì)影響所有其它量子比特，從而使量子計(jì)算相比于經(jīng)典計(jì)算機(jī)具有極大的并行加速能力。

要實(shí)現(xiàn)量子加速，參與計(jì)算的量子比特必須處于量子相干狀態(tài)中。當(dāng)前，受限于工程技術(shù)能力，人們所建造的量子相干系統(tǒng)所能維持的相干狀態(tài)時(shí)間不超過(guò)一秒，且隨著量子比特?cái)?shù)的增多，系統(tǒng)與周?chē)h(huán)境相互影響越來(lái)越大，保持相干態(tài)也越來(lái)越困難。

除了要保持相干態(tài)外，環(huán)境中的各種噪音都可能干擾量子計(jì)算，因此它還面臨著噪聲干擾導(dǎo)致的出錯(cuò)問(wèn)題。由于量子比特一旦觀測(cè)就會(huì)坍塌到一個(gè)特定狀態(tài)，無(wú)法通過(guò)直接觀測(cè)特定的量子比特來(lái)確定是否出錯(cuò)。為建造一個(gè)具有自我糾錯(cuò)能力的邏輯量子比特，需要更多的實(shí)際量子比特，距離建造出可實(shí)用的量子計(jì)算機(jī)還有很大的距離。

經(jīng)典計(jì)算問(wèn)題本質(zhì)上是一系列算符操作，可以通過(guò)門(mén)電路來(lái)實(shí)現(xiàn)。談到量子計(jì)算也是類(lèi)似，我們對(duì)應(yīng)著 n 個(gè) qubit， 對(duì)其執(zhí)行一系列算符操作，最后執(zhí)行測(cè)量得到計(jì)算結(jié)果。如圖6，我們常常畫(huà)出橫著并排的 n 條直線，從左到右代表著時(shí)間順序，而不同的直線代表不同的 qubit；在這些直線上排列著各種小方塊大方塊還有豎線，代表著各種不同的單 qubit 或多 qubit 幺正算符，每一個(gè)幺正算符被稱為一個(gè)（量子）門(mén) U；主要的幾種量子門(mén)如翻轉(zhuǎn)門(mén) σX，Hadmard 門(mén) H、控制非門(mén)等，人們可以將一些簡(jiǎn)單的量子門(mén)組合成更復(fù)雜的量子門(mén)；整張圖就被稱為一個(gè)量子網(wǎng)絡(luò) / 量子電路[圖6]。

圖6.由量子門(mén)組成的復(fù)雜量子電路

1994年，Peter Shor 提出了一個(gè)能在多項(xiàng)式時(shí)間內(nèi)分解給定整數(shù)的量子算法[2]。這意味著，一個(gè)具有足夠量子比特?cái)?shù)的量子計(jì)算機(jī)可以破解RSA 算法。2001年，IBM的研究人員在基于核磁共振的7量子比特計(jì)算機(jī)上實(shí)現(xiàn)整數(shù)15的素因子分解，到2014年人們已可在量子計(jì)算機(jī)上運(yùn)行Shor算法分解整數(shù)56153。RSA算法是當(dāng)前廣泛使用的公鑰密碼體制之一，隨著量子計(jì)算機(jī)能力的增強(qiáng)，此類(lèi)公鑰密碼體制的安全性將受到嚴(yán)重威脅。

1996年，貝爾實(shí)驗(yàn)室科學(xué)家Lov Grover提出Grover量子搜索算法[3]。對(duì)于一個(gè)無(wú)序數(shù)據(jù)庫(kù)，最優(yōu)的經(jīng)典算法的搜索復(fù)雜度為O(N)，而該搜索算法可將搜索復(fù)雜度降低至，從而對(duì)于經(jīng)典分組密碼算法的窮舉攻擊可以起到平方加速的作用。例如，對(duì)AES-128算法的窮舉攻擊，經(jīng)典計(jì)算機(jī)下的復(fù)雜度為2128，而使用Grover算法在量子計(jì)算機(jī)的復(fù)雜度可降低至。

4 結(jié)束語(yǔ)

自從經(jīng)典計(jì)算機(jī)出現(xiàn)，模擬電子電路就以促進(jìn)更快的計(jì)算機(jī)設(shè)計(jì)為其任務(wù)之一。同時(shí)，計(jì)算機(jī)的高速發(fā)展也加快了模擬電子電路的進(jìn)步。這一反饋循環(huán)一直在促進(jìn)計(jì)算機(jī)工業(yè)半個(gè)世紀(jì)以來(lái)爆炸式的發(fā)展。量子計(jì)算機(jī)具有潛力把這一爆炸式的發(fā)展轉(zhuǎn)變得更具活力，如同量子計(jì)算機(jī)用于創(chuàng)造更快更有力的量子計(jì)算元件一樣。

自上世紀(jì)八十年代初人們提出量子計(jì)算以來(lái)，從最初的質(zhì)疑到最近幾年IBM、微軟、谷歌、D-Wave等公司不斷刷新量子計(jì)算機(jī)的量子比特?cái)?shù)、計(jì)算能力，量子計(jì)算熱潮持續(xù)不斷。然而到目前為止，人類(lèi)還沒(méi)造出真正意義上的通用量子計(jì)算機(jī)，主要原因在于量子比特的質(zhì)量比數(shù)量更重要：量子比特?cái)?shù)做大并非難事，真正的困難是如何在芯片做大的同時(shí)保證每個(gè)量子比特的相干時(shí)間以及量子邏輯門(mén)和量子測(cè)量的保真度。限于當(dāng)前量子計(jì)算機(jī)的發(fā)展水平，量子計(jì)算機(jī)對(duì)傳統(tǒng)密碼學(xué)的威脅還較小，且人們針對(duì)性地設(shè)計(jì)了一些能抵御量子計(jì)算機(jī)攻擊的密碼算法，儲(chǔ)備了大量的相關(guān)密碼技術(shù)，可緩解量子時(shí)代的信息安全問(wèn)題。另一方面，目前關(guān)于量子密碼的研究還僅局限于量子密鑰分發(fā)，對(duì)基于量子特性的量子密碼算法研究還較少。在大型通用量子計(jì)算機(jī)出現(xiàn)時(shí)，新型量子算法可能出現(xiàn)井噴，人們可以利用量子特性來(lái)提高密碼算法的安全性，也可以利用量子特性對(duì)密碼算法進(jìn)行攻擊。事實(shí)上，從可計(jì)算性的角度看，圖靈機(jī)模型下的可計(jì)算問(wèn)題與量子計(jì)算模型下的可計(jì)算問(wèn)題是等價(jià)的，也就是說(shuō)量子計(jì)算機(jī)的優(yōu)勢(shì)可能只是在計(jì)算復(fù)雜度方面；但是從目前幾個(gè)有效的量子加速算法看，在大幅度降低計(jì)算復(fù)雜度的同時(shí)，其空間復(fù)雜度卻呈現(xiàn)快速增長(zhǎng)。在處理很多規(guī)模巨大的實(shí)際問(wèn)題時(shí)，我們關(guān)心的復(fù)雜度=時(shí)間復(fù)雜度×空間復(fù)雜度，在這個(gè)意義下如果某種加速算法雖然時(shí)間很快，但同時(shí)帶來(lái)空間復(fù)雜度指數(shù)級(jí)增長(zhǎng)，那么要想突破解決實(shí)際問(wèn)題計(jì)算上瓶頸的作用就非常有限。因此，未來(lái)量子計(jì)算機(jī)能給人類(lèi)社會(huì)帶來(lái)怎樣的沖擊，我們將拭目以待。

名詞解釋：

幺正算符：對(duì)一個(gè)矩陣，如果該矩陣乘以它的伴隨矩陣等于單位陣，則稱該矩陣為幺正算符。

量子糾纏：量子糾纏是是一種量子力學(xué)現(xiàn)象，它描述了兩個(gè)粒子互相糾纏，即使相距遙遠(yuǎn)距離，一個(gè)粒子的行為將會(huì)影響另一個(gè)的狀態(tài) 。