通向量子計算和量子信息之路

量子信息學是量子力學與信息科學、計算機科學的交叉學科。美國生物學家E.O.威爾遜（Edward O. Wilson）有一段話很好地說明了交叉學科的重要意義，他說：“科學是我們時代最大膽的形而上學，是人類的創(chuàng)造，相信如果我們有夢想，堅持去發(fā)現(xiàn)、解釋、再夢想，從而不斷進入新的領地，讓世界顯得更清晰，我們就能掌握宇宙的真正奇異之處，而這些奇異之處將會被證明是互相聯(lián)系，有意義的。”量子信息就是宇宙的一個奇異之處，反映了信息與物質的深刻聯(lián)系。

不同學科的科學家給交叉學科帶來各自的特長。大數(shù)學家希爾伯特有一句幽默的名言：“物理學如此重要，不能留給物理學家?！笔聦嵣希柌貙V義相對論的數(shù)學形式做出過重要貢獻，當時對愛因斯坦構成競爭，讓愛因斯坦感到很大壓力。類似地，物理學家可以說，生物學是如此重要，不能全留給生物學家。事實上，正是物理學家協(xié)助開啟了分子生物學。

物理學家還可以說，信息和計算是如此重要，不能全留給計算機科學家。這正是本文所要回顧的。我們將追溯物理學家所走的信息之路，從經典信息到量子信息。

量子信息并不是指經典信息技術的量子物理基礎，雖然物理學對經典信息提供了硬件基礎，電子計算機的器件（晶體管、存儲器等）中的電子也確實服從量子力學。量子計算也不是指關于量子力學的計算問題，不是計算物理。這些固然是重要的領域，但不是所謂的量子計算與量子信息。

什么是信息

信息的英文是information。顧名思義，信息是被告知的東西（Information is that which informs）。 信息是訊息（message）的內容，是對我們在獲得該訊息之前對它的無知程度的度量，是對不確定性的降低。當我們對于某件事的不確定性越大，就需要越多的信息來消除這個不確定性。信息的一個性質是，它可以編碼成各種形式。比如，同樣的思想可以用不同語言來表達。信息論中，信息用一個字符串來表達。

信息不僅是個抽象的數(shù)學概念。信息離不開物理載體，又可在不同物理載體之間轉換。信息處理過程是物理過程，受物理規(guī)律主宰。比如，由聲音傳遞的信息取決于空氣和耳膜的振動，由文字表達的信息取決于粉筆灰或墨水的分布；磁存儲的信息取決于磁疇的狀態(tài)；生命信息取決于遺傳物質中四種堿基的分布；神經網絡中的信號取決于神經元的狀態(tài)。

1991年，蘭道爾（Rolf Landauer）提出一個口號——信息是物理的——倡導從物理的角度研究計算和信息。1990年，惠勒（John Wheeler）提出一個口號——物質來自比特?；堇蘸吞m道爾的思想影響了最早研究量子信息的一批人，可以稱他們?yōu)榱孔有畔W的祖父。

順便提一下，1972年，安德森（Phil Anderson）曾提出：“多了就是不一樣”。是說，多體系統(tǒng)會展現(xiàn)出少體系統(tǒng)沒有的新性質。從信息和量子信息的角度考慮物理定律的層展，也是一個有意思的方向。

麥克斯韋妖

最早進入物理學的信息問題，可能是麥克斯韋妖佯謬。1867年，麥克斯韋在一封信里提出這個佯謬。他在1871年出版的《熱的理論》（Theory of Heat）一書中，做了詳細論述?？紤]封閉容器內處于恒溫的氣體，他寫道：“假設這樣的一個容器分成兩半，A和B，隔板上有一個小洞，有一個有意識的存在（being）能夠看到單獨的分子，能夠關閉或打開這個洞，從而讓較快的分子從A運動到B，讓較慢的分子從B運動到A。因此他不需要做功，就能提高B的溫度，降低A的溫度。這與熱力學第二定律矛盾。1879，湯姆遜（William Thomson，也就是開爾文勛爵）將麥克斯韋假想的being稱為麥克斯韋妖。

麥克斯韋（James Clerk Maxwell，1831—1879）

1929年，作為博士論文，西拉德（Leo Szilard）研究了麥克斯韋妖問題。他用比特表示分子的位置狀態(tài)，涉及了信息。（這里比特指容器的左右，他沒有用比特和信息這些名詞。）西拉德提出麥克斯韋妖測量分子狀態(tài)時，消耗能量，熵增加了kBln2，抵消了氣體分子的熵減少。這里kB代表玻爾茲曼常數(shù)。

西拉德還提出一種利用信息的熱機，也就是說，可以從信息提取功。我們用查爾斯·本內特（Charles Bennett）在1987年提出的版本來討論。考慮一個恒定溫度的熱庫接觸的小車，以及一串小隔間組成的傳送帶，每個小隔間里面有一個分子。假設事先知道每個分子的位置狀態(tài)（信息），也就是在小隔間的左半部或者右半部。相應地，就可以設計機械，利用活塞向右半部或者左半部移動，分子所在的空間增加到整個小隔間。從而分子總是對外做功，驅動小車運動。也就是說，信息轉化為功。如果事先不知道分子的位置，平均做功為零。

信息論

1948年，香農（Claude Shannon）借助熵的概念，提出了信息論?？紤]一個字母表，由a1，a2， ...， an組成，每個字母出現(xiàn)的概率分別是p1，p2，...，pn，p1+p2+...+ pn=1。香農定義了信息熵:H=-p1log2（p1） -p2log2（p2） ...-pnlog2（pn）。這里log2代表以2為底的對數(shù)。香農證明了這n個字母組成的訊息可以壓縮到nH比特。也就是說，信息熵代表平均每個字母的信息量，定量刻畫了信息存儲與傳輸所需的資源。

我們可以看出，如果p1=1， 其他的pi=0，也就是說只有a1這一個字母出現(xiàn)，那么H=0， 也就是說沒有信息量；如果每個pi都等于1/n， 那么H=log2n，這是最大值。

蘭道爾原理

從20世紀30年代開始，計算機的基礎理論和技術有很多發(fā)展。1961年，蘭道爾在IBM工作時提出了蘭道爾原理：每刪除一個比特的信息，環(huán)境的熵至少增加kBln2，也就是說，至少需要耗散能量kBTln2。我們知道，熵乘以溫度T就是熱量，也就是耗散到環(huán)境的能量。

1973年，本內特提出可逆計算的概念，指出原則上不需要能耗。雖然很多邏輯運算是不可逆的，比如2+3和1+4都等于5，因此從輸出結果5，不能唯一確定輸入。但是不可逆運算可以嵌套在可逆運算中，也就是將輸入信息也當作輸出結果的一部分。1982年，他提出可逆圖靈機模型。圖靈機是最簡單的計算模型。

在這些工作的基礎上，1987年，本內特給出了麥克斯韋妖佯謬的解決方案——對分子狀態(tài)的測量本身可以不消耗能量，測量結果存儲在妖的記憶中，氣體的熵減少由妖的記憶的熵增加補償。但是妖的記憶有限，為了存儲新的測量結果，需要刪除舊的記憶，因此必須將熵轉移到環(huán)境，也就是說，必須耗散能量到環(huán)境中去。因此耗散的能量不是來自測量信息，而是來自刪除信息。當然，如果將氣體、妖、環(huán)境一起考慮，總熵總是不減少的。

信息與能量

作為對前述若干概念的消化，我們看一下信息與能量的關系。如果事先知道某訊息（一串比特，比如各分子的位置）的內容，刪除這個訊息不需要消耗能量。

例如，考慮一個盒子中有一個分子，如果知道它在盒子的哪半邊，可設法用一個小盒子包住它，它對小盒子的每個壁都有碰撞，平均做功為零，因此我們在不做功的情況下將它轉移到事先選好的盒子的一半（事先選定左邊或者右邊），也就是刪除訊息。因此，知道信息后，可以不費能量將其刪除。而且，前面說過，還可以利用它，讓分子對外做功。

但是，如果不知道分子位置時，我們只能統(tǒng)一地將盒子體積壓到一半（事先選定左邊或者右邊）。這需要付出能量。

計算機極簡史

19世紀的查爾斯·巴貝奇（Charles Babbage）設計了兩個機械計算機，雖然都沒能實際完成。19世紀20年代，巴貝奇設計了計算多項式函數(shù)的差分機。1837年，他又設計了可編程的機械計算機Analytic Engine，包含了計算機的主要元素。1941年，有人實現(xiàn)了他的設計。

巴貝奇制作的Analytic Engine的模型

詩人拜倫的女兒阿達·洛芙萊斯（Ada Lovelace）為Analytic Engine寫了程序，成為歷史上第一位程序員。巴貝奇和洛芙萊斯的照片曾經放在一起，作為英國50英鎊新鈔票上的候選人物。但最終，另一位候選人阿蘭·圖靈（Alan Turing）勝出。

圖靈被選為50英鎊新鈔票上的人物

1937年，圖靈提出了圖靈機、普適圖靈機和圖靈假說，嚴格定義了計算和程序的概念。圖靈假說是說，存在普適圖靈機，可以模擬任何圖靈機。這就是說，存在普適計算機，用程序就可以實現(xiàn)任何計算。

1939年，物理學家約翰·阿塔納索夫（John Vincent Atanasoff）與他的學生克利福德·貝里（Clifford Berry）建造了第一臺電子計算機。這是一臺特定目的的計算機，不能編程。它用二進制和布爾代數(shù)，能計算29個聯(lián)立方程。硬件上，它由電子真空管實現(xiàn)計算，用電容器作內存，沒有中央處理器（CPU）。

物理學家約翰·莫克利（John Mauchly ）和艾克特（J. P. Eckert）設計了世界上第一臺電子通用計算機，即ENIAC （Electronic Numerical Integrator And Computer，電子數(shù)值積分計算機），1946年建成。ENIAC的第一個用途是馮·諾依曼和烏拉姆的氫彈計算。莫克利多次訪問過阿塔納索夫，但是1944年之前，沒有告知后者自己也在造計算機。這使得莫克利后來沒有獲得專利。

電子計算機飛速發(fā)展。20世紀50年代，每秒做1 000次浮點運算。而現(xiàn)在的速度是148.6P FLOPS（P = 1012）。1965年，戈登·摩爾（Gordon Moore）總結出所謂的“摩爾定律”：單個集成電路芯片上的晶體管數(shù)目大約每兩年翻一番。從下圖可以看出，摩爾定律延續(xù)多年。

晶體管越來越小，越來越快。如此下去，單個比特只需要原子尺寸。但是在原子尺寸，量子效應將起支配作用，適用于經典計算機的摩爾定律也就不能延續(xù)。

所以，一個思路就是，變不利為有利，干脆用量子力學作為新的計算（邏輯）原理。利用量子力學的原理，特別是量子態(tài)疊加原理，完成計算任務，處理和傳遞信息，這就是所謂的量子計算與量子信息。

量子力學基本問題的研究

量子計算與量子信息又與量子力學基本問題密切關聯(lián)。量子糾纏是超越任何經典關聯(lián)的量子特性，研究始于愛因斯坦等人，經過戴維·玻姆（David Bohm）等人，后來由約翰·貝爾（John Bell）取得突破。

單量子系統(tǒng)在這些研究中體現(xiàn)出重要性。以前，正如薛定諤所說，我們從來不用單個電子或原子或小分子做實驗。在思想實驗中，我們有時候假設能夠做，這不可避免導致奇怪的后果……

事實上，當年的思想實驗今天已經成為真實的實驗，對于奇怪后果的探究導致量子物理基礎和量子信息的進展。

量子計算與量子信息的興起

1978年，保羅·貝尼奧夫（Paul Benioff）提出一個量子力學模型，實現(xiàn)經典圖靈機的每一步過程。1982年，費曼提出，用經典計算機模擬量子過程需要指數(shù)級資源，而量子計算機則可以有效地模擬量子過程。蘇聯(lián)的馬寧（I.Manin）也有類似的想法。1983年，阿爾伯特提出量子元胞自動機。

1985年，英國物理學家戴維·多伊奇（David Deutsch）提出量子圖靈機和普適量子圖靈機的概念。1989年，他又提出由量子門組成的量子計算的線路模型。

作為一個有實用意義的突破，1994年，美國計算機科學家彼得·肖（Peter Shor）提出有效解決素數(shù)因子分解（尋找奇數(shù)的素數(shù)因子）的量子算法。在經典計算中，這個問題是一個NP問題，也就是說，需要的時間不是數(shù)字的二進制位數(shù)n的多項式函數(shù)。事實上，需要的時間是exp（O（n3（log（n）2/3））。而肖的量子算法需要的時間只是O（n2log（n） loglog（n））。f=O（g）的意思是，|f/g|介于兩個有限正數(shù)之間。 量子計算的算法基于糾纏態(tài)的運用。量子糾纏也導致量子通信，比如量子隱形傳態(tài)。而量子密碼的某些方案基于海森堡不確定關系，某些方案基于量子糾纏。

2017年，意大利的國際理論物理中心將狄拉克獎授予本內特、多伊奇和肖，以表彰他們用量子力學的基本概念解決計算和信息的基本問題，從而將量子力學、計算機科學和信息聯(lián)系在一起。

小結

信息是物理的。因此經典計算和經典信息基于經典物理，而量子物理導致量子計算和量子信息。突破摩爾定律的需要，經典信息和經典計算的量子推廣，量子力學基本問題的探究，形成合力，催生了量子信息和量子計算。