19. 什么是經(jīng)典計(jì)算機(jī)的運(yùn)算極限？

（What Are the Limits of Conventional Computing?）

    （本文來自科學(xué)網(wǎng)張林的博客）

乍一看，傳統(tǒng)計(jì)算機(jī)的運(yùn)算極限似乎只是一個(gè)工程問題。傳統(tǒng)計(jì)算機(jī)的運(yùn)算極限不就決定于你能輸入多少能量而不至于把芯片融化？不就決定于你在硅存儲(chǔ)器里翻轉(zhuǎn)一個(gè)比特的最高速度? 不就決定于你在一個(gè)房間大小的空間里能把電腦做得多大? 所以，傳統(tǒng)計(jì)算機(jī)的運(yùn)算極限這個(gè)問題表面上看似乎并不深?yuàn)W。  

 然而事實(shí)上，運(yùn)算(computation)的概念遠(yuǎn)比怎樣更好地制造一臺(tái)計(jì)算機(jī)更加地抽象和基礎(chǔ)。早在 20世紀(jì)30年代中期，普林斯頓數(shù)學(xué)家阿朗佐·丘奇(Alonzo Church)和艾倫·圖靈(Alan Turing)就已經(jīng)證明，任何涉及比特和字節(jié)的計(jì)算都可以在一個(gè)被稱為圖靈機(jī)(Turing machine)的理想化計(jì)算機(jī)上完成，也就是任何傳統(tǒng)計(jì)算都能在圖靈機(jī)的框架下進(jìn)行。 這個(gè)結(jié)果表明所有的經(jīng)典計(jì)算機(jī)本質(zhì)上都等價(jià)為圖靈機(jī)，這一發(fā)現(xiàn)使科學(xué)家和數(shù)學(xué)家能夠提出關(guān)于計(jì)算的更為基本的問題而不必糾纏于計(jì)算機(jī)架構(gòu)的細(xì)枝末節(jié)。

 例如，理論學(xué)家現(xiàn)在已經(jīng)把計(jì)算問題在更為廣泛的意義上分成兩大類：P問題和NP問題。 一般來說，P問題是那些可以快速解決的問題，也就是能夠在多項(xiàng)式（Polynomial）時(shí)間內(nèi)算出結(jié)果的問題（更嚴(yán)格的表述是存在多項(xiàng)式時(shí)間算法的問題）。例如對(duì)一個(gè)名單按字母的順序進(jìn)行排序的問題，就是典型的P問題，也就是說排序運(yùn)算的時(shí)間和名單上名稱的個(gè)數(shù)n（廣義地稱為運(yùn)算規(guī)模）是多項(xiàng)式的關(guān)系。而 NP問題則更難解決，也就是你算出結(jié)果的時(shí)間和你的運(yùn)算規(guī)模n之間不再是多項(xiàng)式關(guān)系，比如變成指數(shù)關(guān)系：2ⁿ（嚴(yán)格來講NP問題是不確定有沒有多項(xiàng)式算法的問題，英文為：Nondeterministic polynomial problems）。NP問題雖然難以運(yùn)算但其有另外一個(gè)重要特點(diǎn)就是：一旦你知道了答案，檢查這個(gè)答案的對(duì)錯(cuò)卻是相對(duì)容易和快速的（可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證其解是否正確）。NP問題的一個(gè)典型例子是旅行推銷員（或者郵遞員、派送員）問題，即派送員需要把貨物派送到一系列地點(diǎn)，那么他如何在這些地點(diǎn)上尋找一條最短的可能路線？尋找這條最短路徑的運(yùn)算時(shí)間和地點(diǎn)個(gè)數(shù)n之間就似乎不再是多項(xiàng)式關(guān)系（顯然遍歷n個(gè)地點(diǎn)的所有路徑有n!個(gè)）。因?yàn)槟壳八幸阎墨@得答案的算法都不是多項(xiàng)式時(shí)間，都是需要耗費(fèi)大量計(jì)算資源才能完成的算法，即便面對(duì)一個(gè)派送規(guī)模n相對(duì)較小的派送問題，其運(yùn)算量也能超出任何經(jīng)典計(jì)算機(jī)的運(yùn)算能力。  

 然而數(shù)學(xué)家們已經(jīng)證明，如果你能找到一個(gè)快速而簡單的捷徑來解決任何一類NP問題中最難的那個(gè)NP問題，那么你就能解決所有這類NP問題。 所以從這個(gè)意義上，NP問題就會(huì)轉(zhuǎn)化為P問題， 但我們不確定是否存在這樣的捷徑和算法，也就是：是否P = NP。更為清楚的表述就是：那些在多項(xiàng)式時(shí)間內(nèi)能被驗(yàn)證答案的NP問題是否就是能在多項(xiàng)式時(shí)間內(nèi)找到答案的P問題？然而科學(xué)家們并不認(rèn)為P = NP，而數(shù)學(xué)家們要想證明這一點(diǎn)卻并不那么容易。目前這個(gè)問題已經(jīng)成為數(shù)學(xué)中最大的一個(gè)未解之謎，被美國著名克雷數(shù)學(xué)研究所(Clay Mathematics Institute, 簡稱CMI)列為千禧年七大數(shù)學(xué)問題之一。

 然而事情還遠(yuǎn)不如此。20世紀(jì)40年代，貝爾實(shí)驗(yàn)室的科學(xué)家克勞德·香農(nóng)(Claude Shannon)證明：比特不僅適用于計(jì)算機(jī)，它還是描述從一個(gè)物體流向另一個(gè)物體的信息的基本單位。 有一些物理的規(guī)律決定了一個(gè)比特從一個(gè)地方傳遞到另一個(gè)地方的速度，決定了有多少信息可以在一個(gè)給定的通信信道上來回傳輸，以及從內(nèi)存中刪除一個(gè)比特需要多少能量。 香農(nóng)發(fā)現(xiàn)所有處理經(jīng)典信息的機(jī)器都必須遵守這些物理法則（香農(nóng)法則）。顯然對(duì)我們?nèi)四X來說，由于信息在我們的大腦中的確也是來回不斷傳輸和跳動(dòng)的，那么這個(gè)信息法則是否意味著我們?nèi)祟惖乃枷胍沧罱K可以簡化為比特和字節(jié)? 難道我們?nèi)祟愡@么復(fù)雜精密的大腦也只不過是一臺(tái)運(yùn)行的經(jīng)典計(jì)算機(jī)? 顯然這是一個(gè)令人不安的想法。 

  但是在經(jīng)典計(jì)算機(jī)之外還有一個(gè)領(lǐng)域超越了上面對(duì)運(yùn)算速度和信息傳輸?shù)南拗疲蔷褪橇孔印?nbsp;量子理論的概率屬性允許原子或其他量子單元能存儲(chǔ)和處理和經(jīng)典二進(jìn)制不同的信息，這些信息不僅可以是二進(jìn)制里的0或1，也可以同時(shí)是0和1（0和1的疊加態(tài)）。目前，世界各地的物理學(xué)家們正在各地的實(shí)驗(yàn)室里制造著最原始的量子計(jì)算機(jī)并取得了一些階段性的進(jìn)展，他們希望利用量子計(jì)算機(jī)獨(dú)特的量子效應(yīng)來完成傳統(tǒng)經(jīng)典計(jì)算機(jī)無法完成的任務(wù)，比如通過更少的訪問在數(shù)據(jù)庫中快速找到目標(biāo)記錄（Grover的量子搜索算法），利用量子特性快速地進(jìn)行大數(shù)分解（Shor的大數(shù)分解算法）（需要說明的是在量子算法下NP問題變成了P問題）。 但是科學(xué)家們?nèi)栽谠噲D弄清楚到底是什么原因讓量子計(jì)算機(jī)運(yùn)算能力和信息處理能力變得如此強(qiáng)大，并希望在更為可靠的原理上設(shè)計(jì)和制造出具有足夠規(guī)模（足夠量子比特?cái)?shù)）的量子計(jì)算機(jī)來做一些具有實(shí)際應(yīng)用的事情。 

 通過認(rèn)識(shí)量子世界奇異的量子特性和量子邏輯并利用它們來進(jìn)行一些實(shí)際問題的計(jì)算，科學(xué)家們正在更加深入地研究亞原子量子世界的基本規(guī)律。 也許一些看似平凡的事情，比如對(duì)經(jīng)典計(jì)算機(jī)運(yùn)算極限的不斷超越和對(duì)經(jīng)典計(jì)算機(jī)運(yùn)算能力的不斷提升，可能最終會(huì)導(dǎo)致人類對(duì)量子領(lǐng)域更為全新的認(rèn)識(shí)和理解。

                                                               ——CHARLES SEIFE 撰文，張林 編譯