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

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

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

破譯密碼

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

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

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

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

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

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

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

復(fù)雜性問(wèn)題

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

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

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

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

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

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

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

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

答案是肯定的。一個(gè)例子是“大海撈針”問(wèn)題，它指的是從龐大無(wú)規(guī)律的數(shù)據(jù)庫(kù)中找到特定的信息。試想，從包含n個(gè)條目的電話號(hào)碼簿中搜索一個(gè)特定的號(hào)碼而不是一個(gè)特定的名字。這是一個(gè)需要消耗大量時(shí)間的任務(wù)，因?yàn)樘?hào)碼是無(wú)規(guī)則的，它不像名字一樣是按規(guī)律排列的。經(jīng)典計(jì)算機(jī)除了一個(gè)一個(gè)的檢索號(hào)碼之外沒(méi)有其他辦法，最壞的情況是，我們發(fā)現(xiàn)電話號(hào)碼簿中根本不存在我們要找的號(hào)碼，或者這個(gè)號(hào)碼處于最后一個(gè)位置，這樣就需要進(jìn)行n次操作。而量子計(jì)算機(jī)只需要n0.5次操作。這看起來(lái)并沒(méi)有提速多少，但是當(dāng)n足夠大時(shí)，提速是相當(dāng)可觀的：以n=1000000為例，經(jīng)典計(jì)算機(jī)需要進(jìn)行一百萬(wà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ù)的增長(zhǎng)，描述分子系統(tǒng)所需的信息量呈指數(shù)增長(zhǎng)，這使得計(jì)算變得異常困難。“它具有指數(shù)級(jí)的復(fù)雜性，”Jozas說(shuō)，“盡管是面對(duì)相對(duì)小的分子，最好的經(jīng)典計(jì)算機(jī)在模擬分子的量子動(dòng)力學(xué)性質(zhì)時(shí)也顯得無(wú)能為力，然而量子計(jì)算機(jī)可以勝任這項(xiàng)工作?！?/p>

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