前奏 - 量子計(jì)算百年風(fēng)云史 “量子比特”何時(shí)統(tǒng)治世界？

　　前奏

　　19世紀(jì)的英帝國(guó)國(guó)力昌隆，在科學(xué)領(lǐng)域，英國(guó)同樣也群星璀璨，在麥克斯韋震古爍今的電磁理論醞釀?wù)Q生的同時(shí)，查爾斯·巴貝奇（Charles Babbage）也在不斷失敗的處境中嘗試著完成差分機(jī)和分析機(jī)，盡管至死都沒有完成設(shè)備的組裝和完整運(yùn)行，但是，這些能夠通過邏輯化的運(yùn)作進(jìn)行復(fù)雜數(shù)學(xué)運(yùn)算的設(shè)備雛形卻使得人們認(rèn)識(shí)到通用計(jì)算機(jī)的可能性。

　　1936年，阿蘭·圖靈提出了現(xiàn)代計(jì)算機(jī)的概念。 （來(lái)源：NPL/Science Museum）

　　1936年，阿蘭·圖靈（Alan Turing）在論文《論數(shù)字計(jì)算在決斷難題中的應(yīng)用》（On Computable Numbers， with an Application to the Entscheidungsproblem）里提出了現(xiàn)代計(jì)算機(jī)的概念，天才的圖靈是如此描述這樣的設(shè)備的：“發(fā)明一臺(tái)用來(lái)計(jì)算所有可計(jì)算數(shù)列的設(shè)備是完全可能的。”

　　1944年，世界上第一臺(tái)電子數(shù)字可編程計(jì)算機(jī)巨人（Colossus）在英國(guó)問世，它的用途就是為了破解德軍通信密碼，在冷戰(zhàn)期間，為了掩蓋英國(guó)有能力破解洛倫茲密碼機(jī)（Lorenz Cipher）的事實(shí)，丘吉爾下令銷毀絕大部分巨人計(jì)算機(jī)。1946年，ENIAC在美國(guó)曝光，在戰(zhàn)時(shí)，這臺(tái)設(shè)備設(shè)計(jì)之初的主要目的就是來(lái)計(jì)算火炮射表，而它最早承擔(dān)的項(xiàng)目還包括計(jì)算熱核武器的可行性。

　　隨著戰(zhàn)爭(zhēng)結(jié)束以及社會(huì)各行各業(yè)的復(fù)興需求，體積龐大但在運(yùn)算上有著驚人優(yōu)勢(shì)的計(jì)算機(jī)從戰(zhàn)爭(zhēng)期間的隱蔽戰(zhàn)線開始越來(lái)越多地出現(xiàn)在民用和商業(yè)領(lǐng)域。

　　1951年，費(fèi)朗替（Ferranti）公司為曼徹斯特大學(xué)開發(fā)出了世界上第一臺(tái)商用計(jì)算機(jī)Ferranti Mark 1，同年，美國(guó)人口調(diào)查局采購(gòu)了UNIVAC I，這是世界上第一臺(tái)被大規(guī)模制造的計(jì)算機(jī)，僅僅3年之后，IBM 推出了“相對(duì)”而言更小更便宜的計(jì)算機(jī)IBM 650 ，這臺(tái)設(shè)備凈重超過900千克，算上電力供應(yīng)裝置之后則在1.35噸以上，售價(jià)高達(dá)50萬(wàn)美元或者每月租金為3500美元。

　　1947年，雙體性晶體管問世，并逐漸取代真空管在以往計(jì)算機(jī)設(shè)計(jì)中的位置，1953年，世界上第一臺(tái)可運(yùn)行的晶體管計(jì)算機(jī)在英國(guó)問世，兩年后，另一臺(tái)包含200個(gè)晶體管、1300個(gè)固態(tài)二極管的晶體管計(jì)算機(jī)問世。相比真空管，晶體管的體積更小、耗能更少、更穩(wěn)定而且壽命更長(zhǎng)，但是最重要的是，它能容納數(shù)以萬(wàn)計(jì)的邏輯電路。在1952年，集成電路概念首次被杰弗里·達(dá)莫（Geoffrey W.A. Dummer）提出，6年后，世界上第一個(gè)可運(yùn)行的集成電路問世。晶體管和集成電路的出現(xiàn)意味著計(jì)算機(jī)有了更快的運(yùn)行速度和更強(qiáng)大的計(jì)算能力。

　　1965年，英特爾聯(lián)合創(chuàng)始人戈登·摩爾（Gordon Moore）在文章中提出了被后人補(bǔ)充進(jìn)而成型的摩爾定律，10年后，摩爾本人再次對(duì)此定律做出調(diào)整：“在這10年末期，傾斜程度（半導(dǎo)體芯片上集成的晶體管和電阻數(shù)量）將每2年增加大約1倍?！?/p>

　　計(jì)算機(jī)的發(fā)展軌跡按照摩爾的預(yù)言波瀾不驚地前行著，大眾繼續(xù)享受著計(jì)算機(jī)小型化、廉價(jià)化和性能提升帶來(lái)的種種便利優(yōu)勢(shì)。但是，科學(xué)界卻異常焦急，大量新的議題和項(xiàng)目迫切需要計(jì)算能力更加強(qiáng)大的計(jì)算機(jī)設(shè)備幫助，Altas、CDC6600、Cray 兩代以及90年代面世的富士“數(shù)值風(fēng)洞”（Numerical Wind Tunnel）、Hitachi SR2201等超級(jí)計(jì)算機(jī)盡管已經(jīng)在一定程度上解決了科學(xué)家的需求，但是，他們對(duì)當(dāng)時(shí)計(jì)算機(jī)的能力依然感到不滿足而迫切地需要一種新的更加強(qiáng)大、速度更快的計(jì)算機(jī)設(shè)備。

　　匣中的失樂

　　數(shù)學(xué)上，算法是對(duì)函數(shù)進(jìn)行有效計(jì)算的方法，算法研究的一個(gè)重要的切入點(diǎn)是尋找可以有效計(jì)算的函數(shù)，這類函數(shù)叫做遞歸函數(shù)。

　　1931年，哥德爾（Kurt Friedrich G?del）提出并證明了后來(lái)被統(tǒng)稱為哥德爾不完備定理的兩條定理，而根據(jù)哥德爾不完備定理，一些函數(shù)在數(shù)學(xué)上是不能被算法計(jì)算的。

　　哥德爾對(duì)“計(jì)算”（computation）做出了清晰的定義，盡管在論文里這些定義看上去不盡相同，但它們最后都?xì)w于同一類可計(jì)算函數(shù)里。而邱奇-圖靈假想（Church-Turning thesis）做出這樣的判斷，任何在算法上可計(jì)算的函數(shù)都能被圖靈機(jī)計(jì)算。

　　計(jì)算機(jī)科學(xué)家把一個(gè)運(yùn)行時(shí)間隨著輸入大小而像多項(xiàng)式展開那樣增長(zhǎng)的算法叫做“多項(xiàng)式時(shí)間”（polynomial-time），如果一個(gè)問題用多項(xiàng)式時(shí)間就能解決的話，大家就把它稱作復(fù)雜類度為P的問題——絕大多數(shù)P類問題都用有效的算法解決，然而，大多數(shù)不屬于P類的問題無(wú)論花多少時(shí)間也解決不了。

　　按照強(qiáng)邱奇－圖靈假想（Strong Church-Turing Thesis）進(jìn)一步推演的話，就是說(shuō)，如果在物理計(jì)算機(jī)上計(jì)算一個(gè)可計(jì)算函數(shù)的時(shí)間是 T 的話，那么在圖靈機(jī)上的時(shí)間則是O（Tc），而這里的常數(shù) c 僅僅由計(jì)算機(jī)使用的函數(shù)類型決定。

　　隨著數(shù)字計(jì)算機(jī)的出現(xiàn)，由于機(jī)器本身的容量和時(shí)間有限，這就使得可計(jì)算和不可計(jì)算之間的差別在計(jì)算機(jī)的實(shí)際應(yīng)用上顯得越來(lái)越重要，皮特·休爾（Peter Williston Shor）這樣評(píng)價(jià)道，“如果所有計(jì)算機(jī)跑完一個(gè)可計(jì)算函數(shù)的時(shí)間里，太陽(yáng)都燃燒殆盡了，這在實(shí)用方面可一點(diǎn)都不好。”

　　于是，一種新的迥異于傳統(tǒng)算法的計(jì)算機(jī)呼之欲出。

　　1970年，斯蒂文·威斯納（Steven Wiesner）就設(shè)想量子信息處理是解決密碼邏輯認(rèn)為較好的一種方式，這是量子計(jì)算最早的火花。在10多年后，在愛德華·福萊德金（Edward Fredkin）的可逆計(jì)算理念的啟發(fā)下，費(fèi)曼為大家開辟了那條新路。

　　費(fèi)曼相信，一臺(tái)基于量子力學(xué)現(xiàn)象的計(jì)算機(jī)在模仿量子力學(xué)現(xiàn)象上有著近水樓臺(tái)先得月的先天優(yōu)勢(shì)。

　　“自然不是經(jīng)典的，如果你想模擬自然的話，那你最好去用量子力學(xué)。”

　　在1982年發(fā)表的一篇論文中，諾貝爾獎(jiǎng)得主費(fèi)曼認(rèn)為，在計(jì)算機(jī)上模擬量子力學(xué)內(nèi)在地就需要指數(shù)級(jí)增長(zhǎng)的投入，而他給出的建議則是，使用量子計(jì)算機(jī)。費(fèi)曼相信，一臺(tái)基于量子力學(xué)現(xiàn)象的計(jì)算機(jī)在模仿量子力學(xué)現(xiàn)象上有著近水樓臺(tái)先得月的先天優(yōu)勢(shì)——早在1980年，保羅·貝尼奧夫（Paul Benioff）就在論文里提到了基于圖靈機(jī)制造微量子力學(xué)系統(tǒng)計(jì)算機(jī)模型的可能性。

　　1985年，牛津大學(xué)的大衛(wèi)·道勅（David Deutsch）在一篇論文里給出了量子計(jì)算的抽象模型，但是，此時(shí)大家的疑問還是，量子計(jì)算機(jī)究竟能解決哪些實(shí)際問題。7年后，道勅和理查德·約饒（Richard Jozsa）在論文里給出了他們的肯定答案：

　　“比起任何基于確定性算法的經(jīng)典計(jì)算機(jī)，量子計(jì)算機(jī)在解決問題上所花的時(shí)間要少得多；比起任何基于隨機(jī)算法的計(jì)算機(jī)的預(yù)期時(shí)間，量子計(jì)算機(jī)也相對(duì)更少?！?/p>

　　但是僅僅有量子計(jì)算機(jī)的設(shè)想還是遠(yuǎn)遠(yuǎn)不夠的，沒有算法支持的計(jì)算機(jī)無(wú)疑遠(yuǎn)遠(yuǎn)都只能停留在遐想階段，要讓所有人都真正信服量子計(jì)算機(jī)的巨大先進(jìn)性，他們還需要更具說(shuō)服力的事實(shí)。

　　正是從20世紀(jì)90年代開始，量子計(jì)算的研究取得了前所未有的豐碩成果，在各大公司實(shí)驗(yàn)室和院校機(jī)構(gòu)的共同推動(dòng)下，量子計(jì)算從科學(xué)家論文中的設(shè)想、算法逐漸落實(shí)到到實(shí)際制造的機(jī)器上。

　　1994年，貝爾實(shí)驗(yàn)室的休爾發(fā)表了論文，在里面向大家展示了他的量子算法分解大數(shù)的質(zhì)因數(shù)的速度如何領(lǐng)先于當(dāng)時(shí)的已知任何計(jì)算機(jī)——分解一個(gè)1000位的數(shù)字，傳統(tǒng)計(jì)算機(jī)大約需要耗費(fèi)10京（《孫子算經(jīng)》載“萬(wàn)萬(wàn)曰億，萬(wàn)萬(wàn)億曰兆，萬(wàn)萬(wàn)兆曰京”）年的時(shí)間，而利用量子計(jì)算機(jī)的話，只需要20分鐘左右。

　　休爾的量子算法將會(huì)對(duì) RSA 等在內(nèi)的加密算法和系統(tǒng)造成了顯而易見的沖擊，在此以前，破解一個(gè) RSA 129位密碼需要8個(gè)月時(shí)間以及1600名計(jì)算機(jī)用戶，然而用量子算法破解 RSA 140位密碼也只要數(shù)秒的時(shí)間而已。

　　休爾的發(fā)現(xiàn)使得量子計(jì)算機(jī)掀起了一場(chǎng)的風(fēng)暴，不僅席卷了物理學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域，讓他們感受到新的計(jì)算工具蘊(yùn)含的巨大潛力，亦使得包括之前一直相信使用 RSA 算法的國(guó)家部門和各公司開始認(rèn)真對(duì)待關(guān)注這個(gè)概念。

　　量子計(jì)算機(jī)第一次從科學(xué)家的象牙塔里走到了世人面前。

　　1995年，舒馬赫（Benjamin Schumacher）發(fā)表了論文，第一次提出了量子比特信息學(xué)上的概念，并創(chuàng)造了“量子比特”（qubit）的說(shuō)法。

　　比特（bit）是傳統(tǒng)計(jì)算機(jī)中最基礎(chǔ)的構(gòu)件，它只存在兩個(gè)狀態(tài)0或1之間，在量子計(jì)算機(jī)中，情況卻并非如此。量子力學(xué)告訴我們，量子具有疊加態(tài)的特性，因而，量子計(jì)算機(jī)中的比特——即量子比特——同時(shí)就有了0與1的狀態(tài)，它既可以是1，亦可是0?；诹孔悠叫?，我們可以將這兩種狀態(tài)看成是處于兩個(gè)不同宇宙里，那么，當(dāng)一個(gè)量子比特進(jìn)行運(yùn)算時(shí)，實(shí)際上是處于兩個(gè)宇宙里的數(shù)值在同時(shí)執(zhí)行。

　　包含3個(gè)量子比特的寄存器

　　3個(gè)比特可以代表8種狀態(tài)，但是寄存器卻只能記錄其中的一個(gè)結(jié)果，而3個(gè)量子比特構(gòu)成的寄存器同時(shí)也具備了其線性疊加態(tài)效果，于是可以同時(shí)記錄8種數(shù)值結(jié)果。通過這樣一個(gè)簡(jiǎn)單的例子就能看出來(lái)量子計(jì)算機(jī)驚人的計(jì)算能力，是同數(shù)目（設(shè)為n）比特構(gòu)成的經(jīng)典計(jì)算機(jī)的2n倍。

　　理論上來(lái)說(shuō)，一個(gè)量子比特可以儲(chǔ)存的信息是無(wú)限的，當(dāng)被測(cè)量時(shí)，狀態(tài)滿足一些特定條件的量子比特才會(huì)釋出0或1那樣的結(jié)果，也就是說(shuō)，測(cè)量會(huì)使得量子比特從疊加態(tài)坍縮，反之，量子比特中存儲(chǔ)的信息將始終處于動(dòng)態(tài)演化過程之中，并且，通過量子門就能讀取其中的信息。

　　假設(shè)我們?nèi)?shù)字15來(lái)作為要分解的對(duì)象，設(shè)它作N，隨機(jī)選一個(gè)數(shù)字設(shè)作X，并且1《X《N-1，將X當(dāng)做寄存器A中內(nèi)容的指數(shù)然后對(duì)N進(jìn)行模除，余數(shù)則置于寄存器B中，即：

　　我們將這個(gè)運(yùn)算結(jié)果列表如下：

　　我們會(huì)發(fā)現(xiàn)上述取值的運(yùn)算結(jié)果呈現(xiàn)出（1，2，4，8，1，2，4，8……）的重復(fù)數(shù)列，我們將重復(fù)的頻次命為 f，那么這個(gè)運(yùn)算中，f 的取值就是4。

　　通過寄存器B中一系列復(fù)雜的運(yùn)算執(zhí)行，上述的f可以在量子計(jì)算機(jī)中獲得，得出的f值會(huì)帶入下列公式計(jì)算出一個(gè)可能的因數(shù)。得出的結(jié)果不會(huì)一定就是正確的，但是生成f值的量子干涉會(huì)反復(fù)嘗試對(duì)x進(jìn)行代換從而篩選出正確的結(jié)果并排除錯(cuò)誤的答案。

　　這就是休爾的量子算法的整體思路，它向科學(xué)界和大眾真正展示了量子計(jì)算的強(qiáng)大威力。

　　計(jì)算機(jī)科學(xué)中一個(gè)最基本的問題就是非結(jié)構(gòu)化搜索，1996年，貝爾實(shí)驗(yàn)室的拉夫·格羅夫（Lov Kumar Grover）在論文里提出了針對(duì)這一問題的量子算法。假設(shè)有 N 個(gè)黑箱，每個(gè)箱中包含確定的1或0，每次打開一個(gè)箱子記為一次搜索請(qǐng)求，那么如果我們想要尋找到包含1的箱子，那么最多講需要進(jìn)行N次請(qǐng)求，而格羅夫的算法則將其減少到了次。

　　量子計(jì)算機(jī)固然擁有眾多優(yōu)勢(shì)，但是這些基于量子力學(xué)上的特性也使得它本身較之經(jīng)典計(jì)算機(jī)更加不穩(wěn)定。和經(jīng)典計(jì)算機(jī)的設(shè)計(jì)、硬件并不一樣，量子計(jì)算機(jī)的設(shè)計(jì)制造首先需要保證量子比特處于穩(wěn)定的相干疊加態(tài)的之中。

　　量子計(jì)算機(jī)強(qiáng)大的能力是建立在量子相干態(tài)帶來(lái)的量子平行上的，一旦相干態(tài)中的量子比特在和外部環(huán)境發(fā)生量子糾纏之后會(huì)陷入退相干狀態(tài)，那么，此時(shí)的量子比特和傳統(tǒng)比特一樣只能表示一種狀態(tài)，也就是說(shuō)，不穩(wěn)定狀態(tài)下的量子計(jì)算機(jī)和經(jīng)典計(jì)算機(jī)相比喪失了最大的優(yōu)勢(shì)——1995年，休爾和安德魯·斯迪恩（Andrew Steane）分別獨(dú)立發(fā)表了量子糾錯(cuò)的規(guī)劃，試圖以此來(lái)解決量子計(jì)算機(jī)在退相干上的隱患。

　　無(wú)論是休爾還是格羅夫的量子算法實(shí)際上都是建立在量子線路基礎(chǔ)上的，而量子線路和經(jīng)典計(jì)算機(jī)一樣也包含導(dǎo)線——這里的導(dǎo)線在廣義上還包括粒子、光子乃至地域傳送、時(shí)間演化等——和邏輯門，前者用來(lái)傳輸信息，后者則負(fù)責(zé)操作。