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

（What Are the Limits of Conventional Computing?）

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

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

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

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

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

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

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

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

                                                               ——CHARLES SEIFE 撰文,，張林 編譯