如果你在新聞中看到有人成功制造出了量子計(jì)算機(jī)的話，你最好立刻凍結(jié)自己的信用卡。因?yàn)椋?dāng)你在網(wǎng)上購物時(shí)，目前所有保護(hù)你的信用卡信息的方法將會(huì)在幾秒鐘內(nèi)被量子計(jì)算機(jī)攻破。不光是你在銀行內(nèi)的信息，所有的加密信息在量子計(jì)算機(jī)面前都將被輕松破解。

網(wǎng)絡(luò)安全依賴于一些很難解決的數(shù)學(xué)問題

關(guān)于量子計(jì)算機(jī)有很多聳人聽聞的說法，但是量子計(jì)算機(jī)破解加密信息的超強(qiáng)能力是真的?，F(xiàn)有的加密方法是基于那些用普通計(jì)算機(jī)無法快速解決的數(shù)學(xué)問題設(shè)計(jì)的，但是量子計(jì)算機(jī)可以輕易攻破這種加密方法。那么量子計(jì)算機(jī)還有哪些明顯強(qiáng)于普通計(jì)算機(jī)的技能？

破譯密碼

雖然為了回答這個(gè)問題我們進(jìn)行了很多理論方面的準(zhǔn)備，但是這個(gè)問題仍舊很棘手。RSA算法，一種廣泛被用于保護(hù)信息安全的算法，它利用計(jì)算機(jī)都很難快速完成的因數(shù)分解來進(jìn)行加密。如果給你一個(gè)數(shù)字10，你立刻就可以告訴我它可以被分解為2和5兩個(gè)素?cái)?shù)的乘積，但是如果我給你的數(shù)字是62615533，你應(yīng)該無法通過心算告訴我它是哪些素?cái)?shù)的乘積。

這不能怪罪于你的心算能力。一旦數(shù)字足夠大，計(jì)算機(jī)也無能為力?！叭绻o出一個(gè)4000位的數(shù)字，即使是讓現(xiàn)存的計(jì)算機(jī)運(yùn)行和宇宙年齡一樣長的時(shí)間也無法將它分解成一系列素?cái)?shù)的乘積，”劍橋大學(xué)的量子計(jì)算先驅(qū)Richard Jozsa說。

其實(shí)還有其他很多問題和分解數(shù)字具有一樣的特征：我們有很多可以解決它們的算法，但是隨著要解決的問題的難度的增加，所需算法的步數(shù)也越多。另一個(gè)著名的問題是旅行商問題，這個(gè)問題是說如何讓旅行商訪問每個(gè)城市時(shí)所走的路程最短：要訪問的城市越多，問題越復(fù)雜。

復(fù)雜性理論按照解決問題的步數(shù)的增長速度來對(duì)各種問題進(jìn)行分類。如果步數(shù)的增長是指數(shù)型的，比如旅行商問題，問題會(huì)變得非常棘手，因?yàn)橹笖?shù)型增長的增長速度會(huì)越來越快。當(dāng)算法步數(shù)的增長隨著輸入數(shù)字的增加表現(xiàn)成多項(xiàng)式形式時(shí)，我們才認(rèn)為這樣的問題是可解決的：如果輸入的大小是n，解題所需的步數(shù)正比于n2,n3或者nk。雖然解題步數(shù)增長在我們看來還是很快（假設(shè)k=10），但是復(fù)雜理論專家認(rèn)為這種增長還算緩慢?！安綌?shù)增長表現(xiàn)為多項(xiàng)式的數(shù)學(xué)模型是可計(jì)算的，”Jozsa解釋道，“如果步數(shù)增長不表現(xiàn)為多項(xiàng)式的形式，我們認(rèn)為這類問題在實(shí)際操作中是無法解決的?！?/p>

因數(shù)分解被認(rèn)為是不可解決的問題：沒有人寫出可以由我們現(xiàn)在的計(jì)算機(jī)運(yùn)行的多項(xiàng)式時(shí)間（步數(shù)呈多項(xiàng)式型增長）算法。這正是量子計(jì)算可以大展神威之處。1994年數(shù)學(xué)家Peter Shor提出一種解決數(shù)字分解問題的量子算法，它不光是多項(xiàng)式時(shí)間算法，并且k不大于3。這個(gè)算法利用數(shù)論的知識(shí)，將因數(shù)分解問題轉(zhuǎn)化成一種在特定的數(shù)學(xué)函數(shù)中識(shí)別周期模式的問題——模式識(shí)別正是量子計(jì)算機(jī)所擅長的。

如今使用的其他加密算法也存在類似的問題，例如橢圓曲線加密算法（elliptic curve cryptography）：量子計(jì)算機(jī)可以輕易破解它們。

這看起來量子計(jì)算機(jī)有很大優(yōu)勢(shì)，但在這個(gè)領(lǐng)域內(nèi)任何事情都是不確定的。“在復(fù)雜性理論中，要證明給定的任務(wù)不能在多項(xiàng)式時(shí)間內(nèi)解決是出了名的難題，”Jozsa說，“這是一個(gè)尷尬的事實(shí)?！币?yàn)闆]人知道因數(shù)分解的多項(xiàng)式時(shí)間算法，并不意味著這樣一個(gè)等待我們發(fā)現(xiàn)的算法不存在?！耙苍S，下周可能就有一個(gè)聰明的數(shù)論專家把這樣的算法找出來，” Jozsa說，“對(duì)量子計(jì)算來說，這有點(diǎn)掃興?！?/p>

復(fù)雜性問題

復(fù)雜性的等級(jí)

對(duì)于其他問題情況怎么樣？在其他的比因數(shù)分解更難的問題中，量子計(jì)算的威力會(huì)超過經(jīng)典計(jì)算嗎？在回答這個(gè)問題之前我們要明確“更難”的含義，這把我們引導(dǎo)到了復(fù)雜性類（complexity classes）的分級(jí)這里。首先介紹“簡單的”問題，這類問題擁有可在經(jīng)典計(jì)算機(jī)上運(yùn)行的多項(xiàng)式時(shí)間算法，這類問題組成了一個(gè)被稱為P的類。接下來是我們沒有找到多項(xiàng)式時(shí)間算法的問題，但我們可以在多項(xiàng)式時(shí)間內(nèi)來檢驗(yàn)解的正確性。這類問題被稱為NP問題。因數(shù)分解正是屬于這類問題。

在NP類問題中，有一些問題特別難解——這些問題被稱為NP完全問題（NP-complete），旅行商問題屬于這類問題。比NP完全問題更加復(fù)雜的問題這里將不再介紹。

因數(shù)分解被歸納于NP類問題但不屬于NP完全問題。由于量子計(jì)算可以在因數(shù)分解問題中擊敗經(jīng)典計(jì)算，接下來的問題是，當(dāng)涉及NP完全問題時(shí)，量子計(jì)算機(jī)表現(xiàn)如何？有一種說法認(rèn)為，量子計(jì)算機(jī)可以在眨眼之間解決NP完全問題。但這種說法過于樂觀了。“我們不知道我們是否可以用量子計(jì)算機(jī)解決NP完全問題，事實(shí)上，我們認(rèn)為量子計(jì)算機(jī)做不到這一點(diǎn)，”Jozsa解釋道。

P和NP問題是同樣復(fù)雜的問題嗎？

在這里，我們應(yīng)該認(rèn)識(shí)到復(fù)雜性理論的核心問題：所有我們提到的東西都不能被證明。我們不僅不知道量子計(jì)算機(jī)能否有效地解決NP完全問題，甚至不知道普通計(jì)算機(jī)能否有效地解決這些問題。正如可能存在一個(gè)可以解決因數(shù)分解問題但尚未被發(fā)現(xiàn)的多項(xiàng)式時(shí)間算法一樣，也可能存在解決其他NP問題或NP完全問題的多項(xiàng)式時(shí)間算法。如果我們找到了這些算法，那么我們的復(fù)雜性類層次的結(jié)構(gòu)將會(huì)崩潰：P類、NP類和NP完全類將會(huì)屬于同一類。如果你能證明或否定P類問題等價(jià)于NP類問題，那就厲害了，克萊數(shù)學(xué)研究所都會(huì)獎(jiǎng)勵(lì)你一百萬美元：它被認(rèn)為是數(shù)學(xué)中最有趣的七個(gè)開放問題之一。

量子計(jì)算機(jī)會(huì)做什么?

如果理論不是建立在堅(jiān)實(shí)的基礎(chǔ)上,那么我們?cè)鯓颖ＷC量子計(jì)算可以有實(shí)際用處呢？P問題在理論上是“容易”解決的，但是你仍然需要花費(fèi)很多時(shí)間去解決它。這時(shí)量子計(jì)算機(jī)可以幫助我們嗎？

答案是肯定的。一個(gè)例子是“大海撈針”問題，它指的是從龐大無規(guī)律的數(shù)據(jù)庫中找到特定的信息。試想，從包含n個(gè)條目的電話號(hào)碼簿中搜索一個(gè)特定的號(hào)碼而不是一個(gè)特定的名字。這是一個(gè)需要消耗大量時(shí)間的任務(wù)，因?yàn)樘?hào)碼是無規(guī)則的，它不像名字一樣是按規(guī)律排列的。經(jīng)典計(jì)算機(jī)除了一個(gè)一個(gè)的檢索號(hào)碼之外沒有其他辦法，最壞的情況是，我們發(fā)現(xiàn)電話號(hào)碼簿中根本不存在我們要找的號(hào)碼，或者這個(gè)號(hào)碼處于最后一個(gè)位置，這樣就需要進(jìn)行n次操作。而量子計(jì)算機(jī)只需要n0.5次操作。這看起來并沒有提速多少，但是當(dāng)n足夠大時(shí)，提速是相當(dāng)可觀的：以n=1000000為例，經(jīng)典計(jì)算機(jī)需要進(jìn)行一百萬次操作而量子計(jì)算機(jī)僅需要進(jìn)行1000次操作。

分子由大量遵循量子規(guī)律的粒子組成

另一個(gè)量子計(jì)算機(jī)可以大展身手的領(lǐng)域是化學(xué)領(lǐng)域，生物和制藥領(lǐng)域。如果你想理解一個(gè)分子系統(tǒng)，例如為了設(shè)計(jì)一種新藥，一個(gè)明智的選擇就是在計(jì)算機(jī)上模擬它的行為。困難在于分子是由很多粒子組成的，而這些粒子全部遵循量子力學(xué)的規(guī)律。我們知道，隨著粒子數(shù)的增長，描述分子系統(tǒng)所需的信息量呈指數(shù)增長，這使得計(jì)算變得異常困難。“它具有指數(shù)級(jí)的復(fù)雜性，”Jozas說，“盡管是面對(duì)相對(duì)小的分子，最好的經(jīng)典計(jì)算機(jī)在模擬分子的量子動(dòng)力學(xué)性質(zhì)時(shí)也顯得無能為力，然而量子計(jì)算機(jī)可以勝任這項(xiàng)工作。”

密碼學(xué)也會(huì)受益于量子計(jì)算機(jī)。例如，當(dāng)量子態(tài)被觀測(cè)時(shí)就會(huì)發(fā)生塌縮，利用這種性質(zhì)可以監(jiān)測(cè)信息是否被其他人竊取。利用這種方法，人們可以給每個(gè)人分發(fā)量子秘鑰——一串可以用于對(duì)信息加密和解密的字符串。如果有人截獲了秘鑰我們馬上就能知道?！斑@種器件之所以存在，是因?yàn)樗鼈冎恍枰獛讉€(gè)量子比特，因此這屬于量子技術(shù)的范疇。”Jozsa說。這種方法在2007年首次被用于公共實(shí)踐，當(dāng)時(shí)它被用來確保在瑞士日內(nèi)瓦舉行的選舉中的選票安全轉(zhuǎn)移。也許從理論的角度我們很難說量子計(jì)算機(jī)具有什么優(yōu)勢(shì)，但是至少我們知道破壞我們的加密方法是要付出一些代價(jià)的。