量子計算機發(fā)展帶來的思考

.----

量子計算機發(fā)展帶來的思量

----科學技術的創(chuàng)新與發(fā)展

國外究竟為什么能發(fā)明出這些各式各樣的計算機呢？這些意味著

什么呢？作為即將騰飛的的大國怎樣學會這種創(chuàng)新，怎樣在量子信息

發(fā)展的初期占領這塊高地，成為世界科技的引領者？在閱讀一些文

獻論文和熟悉量子信息特殊是量子計算機的發(fā)展的基礎上我做了一

些總結和思量，希翼和大家共同分享、探討上面提出的問題。

量子計算機發(fā)展帶來的思量

——科學技術的創(chuàng)新與發(fā)展

一、引言

自從20世紀30年代以來，圖靈機、計算這些重要的概念在科學的天空中就

向來閃爍著無限的光采。特別是近年來量子計算機、生物計算機、DNA計算等領

域的創(chuàng)新工作引起了了世人的廣泛關注。我們不禁問這樣的問題，國外究竟為什

么能發(fā)明出這些各式各樣的計算機呢？這些意味著什么呢？作為即將騰飛的的

大國怎樣學會這種創(chuàng)新，怎樣在量子信息發(fā)展的初期占領這塊高地，成為世界科

技的引領者？在閱讀一些文獻、論文和熟悉量子信息特殊是量子計算機的發(fā)展的

基礎上我做了一些總結和思量，希翼和大家共同分享、探討上面提出的問題。

二、偉大的創(chuàng)新源于理論

1、計算理論

1.1什么是計算

廣義上講，一個函數(shù)變化如把x變成為了f(x)就是一個計算！如果我們把一

切都看做是信息，那末更精確的講，計算就是對信息的變換！如果采用這種觀

點，我們會發(fā)現(xiàn)，其實自然界充滿了計算！也可以說，計算就是某個系統(tǒng)完成

為了一次從輸入到輸出的變換！這樣理解不要緊，你會發(fā)現(xiàn)，現(xiàn)實世界到處都

是計算了！因為我們徹底可以把所有的自然界存在的過程都抽象成這樣的輸入輸

出系統(tǒng)，所有的大自然存在的變量都看做是信息，于是計算無處不在！也的確,

正是采取了這樣的觀點，國外才有可能發(fā)明什么DNA計算機、生物計算機、量

子計算機這些新鮮玩藝！因為人家把DNA的化學反應、量子世界的波函數(shù)變換都

看做是計算了，自然就會人為地把這些計算組合起來構成計算機了。

1.2圖靈機

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成為

了一個一個的小方格，每一個方格有不同的顏色。有一個機器頭在紙帶上移來

移去。機器頭有一組內(nèi)部狀態(tài)，還有一些固定的程序。在每一個時刻，機器頭

都要從當前紙帶上讀入一個方格信息，然后結合自己的內(nèi)部狀態(tài)查找程序表，

根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進行挪移。

它工作的時候是這樣的：從讀寫頭在紙帶上讀出一個方格的信息，并且根據(jù)

它當前的內(nèi)部狀態(tài)開始對程序進行查表，然后得出一個輸出動作，也就是是否往

紙帶上寫信息，還是挪移讀寫頭到下一個方格。程序也會告訴它下一時刻內(nèi)部狀

態(tài)轉(zhuǎn)移到哪一個。因比，圖靈機只要根據(jù)每一時刻讀寫頭讀到的信息和當前的內(nèi)

部狀態(tài)進行查表就可以確定它下一時刻的內(nèi)部狀態(tài)和輸出動作了。

對圖靈機的計算能力的估價目前普通以強Church-Turing論題為據(jù):任何算

法過程都可以用圖靈機進行有效摹擬。由于隨機算法的引入Church-Turing強論

題后來被修改為更強的論題:任何算法過程都可用概率圖靈機進行有效摹擬。在

這個問題的啟示下，Deutsch與其他一些物理學家認識到，一個數(shù)學問題的計算

復雜性的P與NP分類沒有絕對性，而在此之前人們向來認為這種分類不依賴具體

使用的計算系統(tǒng)。正是這個認識，使得量子計算的研究得到廣泛關注。隨后，

Deutsch提出是否可以用物理學定律推導出任何更強的Church-Turing論題的問

題，Deutsch選用被認為是物理學最基本規(guī)律的量子力學理論進行考慮，提出了

通用量子計算機的概念。

1.3量子圖靈機

正如經(jīng)典計算機建立在通用圖靈機基礎之上，量子計算機亦可建立在量子圖

靈機基礎上.量子圖靈機可類比于經(jīng)典計算機的概率運算.前面提到的通用圖靈

機的操作是徹底確定性的，用q代表當前讀寫頭的狀態(tài)，s代表當前存儲單元內(nèi)

容，d取值為L,R,N分別代表讀寫頭左移、右移或者不動，則在確定性算法中,

當q,s給定時，下一步的狀態(tài)q.,s.及讀寫頭的運動d徹底確定.我們也可以

考慮概率算法，即當q,s給定時，圖靈機以一定的概率6(q,s,q.,s.,d)變換到

狀態(tài)4,s.及實行運動d.概率函數(shù)8(55,4,$.4)為取值［0,1］的實數(shù)，它

徹底決定了概率圖靈機的性質(zhì).經(jīng)典計算機理論證明，對解決某些問題，概率算

法比確定性算法更為有效.量子圖靈機非常類似于上面描述的經(jīng)典概率圖靈機，

現(xiàn)在q,s,q,,s,相應地變成為了量子態(tài)，而概率函數(shù)6(q,s,q.,s.,d)則變成為

了取值為復數(shù)的概率振幅函數(shù)6(q,s,q,,s.,d),量子圖靈機的性質(zhì)由概率振

幅函數(shù)確定正因為現(xiàn)在的運算結果再也不按概率疊加，而是按概率振幅疊加，

所以量子相干性在量子圖靈機中起本質(zhì)性的作用，這是實現(xiàn)量子并行計算的關鍵.

量子計算機可以等效為一個量子圖靈機，但量子圖靈機是一個抽象的數(shù)學模型，

如何在物理上構造出量子計算機呢？

2、物理學基礎(量子力學)

從物理觀點看，計算機是一個物理系統(tǒng)，計算過程是一個物理過程。量子計

算機是一個量子力學系統(tǒng)，量子計算過程就是這個量子力學系統(tǒng)內(nèi)量子態(tài)的演

化過程。量子力學中與量子計算關系最為密切的兩個特性是疊加態(tài)與糾纏態(tài)。由

干量子態(tài)具有量子疊加和量子糾纏的性質(zhì)，便得量子計算有許多不同于經(jīng)典計

算機的新特點。

信息一旦量子化，描述“原子水平上的物質(zhì)結構及其屬性”的量子力學特性

便成為量子信息的物理基礎。此時由于信息載體一一量子的微觀特征，量子化的

信息也變得多姿多彩。這些微觀特征主要表現(xiàn)在：

1)量子態(tài)相干性：微觀系統(tǒng)中量子間相互干涉的現(xiàn)象成為量子信息諸多不

可思議特性的重要物理基礎；

2)量子態(tài)糾纏性：N(大于1)個量子在特定的(溫度、磁場)環(huán)境下可以

處于較穩(wěn)定的量子糾纏狀態(tài)，對其中某個子系統(tǒng)的局域操作會影響到其余子系統(tǒng)

的狀態(tài)；

3）量子態(tài)疊加性：量子狀態(tài)可以疊加，因此量子信息也可以疊加，所以可

以同時輸入或者操作N個量子比特的疊加態(tài)；

4）量子不可克隆定理：量子力學的線性特性確保對任意量子態(tài)無法實現(xiàn)精

確的復制。量子不可克隆定理和測不許原理構成量子密碼技術的物理基礎。

利用量子信息實現(xiàn)通信的過程是使每一個微觀粒子，通過R身的物理特性攜

帶經(jīng)典信息0和1的疊加信號后實現(xiàn)的數(shù)據(jù)傳輸?shù)募夹g。事實上，經(jīng)典計算機也

是量子力學的產(chǎn)物，它的器件也利用了諸如量子隧道現(xiàn)象等量子效應。但僅僅應

用量子器件的信息技術，并不等于現(xiàn)在所說的量子信息。目前的量子信息主要是

基于量子力學的相干特征，重構信息密碼、信息計算和信息通訊的基本原理。

3、第一次的融合（量子計算機與可逆計算）

量子計算機的概念源于對可逆計算機的研究，而研究可逆計算機是為了克服

計算機中的能耗問題.早在六七十年代，人們就發(fā)現(xiàn)，能耗會導致計算機芯片的

發(fā)熱，影響芯片的集成度，從而限制了計算機的運行速度.Lan.dauerTM最早

考慮了這個問題，他考察了能耗的來源，指出：能耗產(chǎn)生于計算過程中的不可逆

操作.例如，對兩比特的異或者操作，因為惟獨一比特的輸出，這一過程損失了

一個自由度。因此是不可逆的，按照熱力學，必然會產(chǎn)生一定的熱量但這種不

可逆性是不是不可避免的呢?事實上，只要對異或者門的操作如圖1所示的簡單

改進，即保留一個無用的比特，該操作就變?yōu)榭赡娴囊虼宋锢碓聿]有限制

能耗的下限，消除能耗的關鍵是將不可逆操作改造為可逆操作（見圖D

a十5

—@——a@b

0—7二@二b

圖1不可逆異或門改進為可逆異或門

Bennett后來更嚴格地考慮了此問題，并證明了，所有經(jīng)典不可逆的計算機

都可以改造為可逆計算機，而不影響其計算能力.因為計算機中的每步操作都可

以改造為可逆操作，在量子力學中.它就可以用一個幺正變換來代表.BcnioffCs

最早用量子力學來描述可逆計算機.在量子可逆計算機中，比特的載體成為二能

級的量子體系，體系處于｛0＞和11＞上，但不處于它們的疊加態(tài).量子可逆計算

機的研究，其核心任務為，對應于具體的計算，尋覓合適的哈密頓量來描述.早

期的量子可逆計算機，實際上是用量子力學語言表述出來的經(jīng)典計算機，它沒有

利用量子力學的本質(zhì)特件.如量子疊加件和相干件.Feymann首先指出16],這

些量子特性可能在未來的量子計算機中起本質(zhì)作用，如用來摹擬量子系

統(tǒng).Deutsehl7找到一類問題，對該類問題，量子計算機存在多項式算法”，而

經(jīng)典計算機則需要指數(shù)算法.但最具哄動性的結果卻是Shor給出的關于大數(shù)因

子分解的量子多項式算法[81（見第三節(jié)），因為此問題在經(jīng)典公鑰體系中有重要

應用Shot的發(fā)現(xiàn)掀起了研究量子計算機的熱潮，從此后，量子計算機的發(fā)展日

新月異.

此外值得指出的是計算與能量的關系。

由熱力學定律知，計算的另一個資源是能量。經(jīng)典計算作為一種機械的這程

與能量的消耗是有關聯(lián)的。在現(xiàn)代的經(jīng)典計算中，計算機消耗電能看似尋常，亦

很少有人研究經(jīng)典計算與能量的關系。然而在量子計算之中，理論上計算是不消

耗任何能量的。熱力學第二定律描述為一個封閉系統(tǒng)的嫡絕不會減少。一個系統(tǒng)

的嫡是該系統(tǒng)的狀態(tài)函數(shù)直覺地說嫡是系統(tǒng)混亂程度的度量若系統(tǒng)越是無規(guī)律

的混亂則其嫡高若系統(tǒng)越是有規(guī)律的整齊，則其嫡越低。對于計算機擦除位信息

與能量或者嫡的關系有‘原理‘，第一形式假設計算機擦除位的信息，散發(fā)到環(huán)

境中的能量的總量至少是，其中，稱為常數(shù),是計算機所在的環(huán)境溫度。原理

第二形式假設計算機擦除位的信息，環(huán)境的嫡增量至少是，其中。是常數(shù)。由

原理可知若在計算中存在信息擦除，則該計算需要能量。在年，經(jīng)典計算機進

行一個基本邏輯運算約消耗能量月。若在計算中不存在信息擦除，則由定律知

計算所消耗的能量沒有下限,也就是說在這種情況下的計算理論上可以不消耗

任何能量。上述陳述成立的關鍵是不擦除信息，是否可以進行計算下面引入可

逆計算的概念。

三、搶占量子計算機研制的高地

1、理論研究

理論上已證明量子圖靈機可以等價為一個量子邏輯電路，因此可以通過一些

量子邏輯門的組合來構成量子計算機.量子邏輯門按其輸入比特的個數(shù)可分為單

比特、二比特、及三比特邏輯門等.因為量子邏輯門是可逆的，所以其輸入和輸

出比特數(shù)相等，量子邏輯門對輸入比特進行一個確定的幺正變換，得到輸出比

特.Deutsch最早考慮了用量子邏輯門來構造計算機的問題.他發(fā)現(xiàn)，幾乎所有

的三比特量子邏輯門都是通用邏輯門.通用邏輯門的含義是指，通過該邏輯門的

級聯(lián)，可以以任意精度逼近任何一個幺正操作.后來不少人發(fā)展了Deutseh的結

果，最后Deutsch和Lloyd各自獨立地證明幾乎所有的二比特量子邏輯門都是通用

的，這里“幾乎”是指，二比特通用量子邏輯門的集合是所有二比特邏輯門的集

合的一個稠密子集.實驗上通常用一些具體的量工邏輯門來構造計算機。Barenco

等人證明，一個二比特的異或者門和對一比特進行任意操作的門可構成一個通用

量子門集。相對來說，單比特邏輯門在實驗上比較容易實現(xiàn)，現(xiàn)在的不少實驗

方案都集中干創(chuàng)造量子異或者門。

2、硬件設計（量子邏輯門的實現(xiàn)）

2.1基本要求

1）可擴展的、具有良好特性的量子位系統(tǒng)

2）能夠初化量子位為某個基態(tài)

3）具有足夠長的相干時間來完成量子邏輯門操作

4）能夠?qū)崿F(xiàn)一套通用量子邏輯門操作

5）能夠測量量子位

6）能夠使活躍量子位和靜止量子位互相轉(zhuǎn)化

7）能夠使活躍量子位準確地在不同的位置之間傳送

2.2幾種方案

1）利用原子和光腔的相互作用

2）利用冷阱束縛離子

3）利用電子或者核自旋共振

2.3量子計算的艱難及其克服途徑

量子計算的優(yōu)越性主要體現(xiàn)在量子并行處理上，無論是量子并行計算還是量

子摹擬，本質(zhì)性地利用了量子相干性.失去了量子相干性，量子計算的優(yōu)越性就

消失殆盡.但不幸的是，在實際系統(tǒng)中，量子相干性卻很難保持.消相干（即量

子相干性的衰減）主要源于系統(tǒng)和外界環(huán)境的耦合.因為在量子計算機中，執(zhí)行

運算的量子比特不是一個孤立系統(tǒng)，它會與外部環(huán)境發(fā)生相互作用，其作用結果

即導致消相干.Unni上定量分析了消相干效應，結果表明，量子相干性的指數(shù)衰

減不可避免.Unruh的分析揭示了消相干的嚴重性，這一結果無疑是對量子計算

機的信奉者的當頭一棒.

因為量子計算機木質(zhì)性地利用了量子相干性，相干性的丟失就會導致運算結

果出錯，這就是量子錯誤.除了消相干會不可避免地導致量子錯誤外，其他一些

技術原因，例如量子門操作中的誤差等，也會導致量子錯誤.因此，現(xiàn)在的關鍵

問題就變成，在門操作和量子存儲都有可能出錯的前提下，如何進行可靠的量子

運算？

Shor在此方向取得一個本質(zhì)性的發(fā)展，這就是量子糾錯的思想。量子糾錯是

經(jīng)典糾錯碼的量子類比。

3、軟件

3.1量子算法

量子計算必須有高效的量子算法才干發(fā)揮其計算優(yōu)勢，目前對量子算法已

經(jīng)有了不少研究。量子并行原理雖然可以僅通過一次變換產(chǎn)生所有計算結果，然

而測量時只能得到一個結果，而且不能選擇所需的結果。量子算法的中心思想是

利用量子態(tài)的相干性，使客觀所需的結果增強，同時使非所需的結果減弱，這

樣客觀所需的結果在測量時就會以相當高的概率浮現(xiàn)。

Geove算法

Shor算法

3.2量子計算機程序設計語言

雖然通用的量子計算硬件量子計算機的創(chuàng)造尚未獲得成功，但以通用量子計

算機為運行載體的通用量子計算機軟件的研究在學術界已經(jīng)有所涉及。由于量子

計算的軟件包括量子操作系統(tǒng)、量子程序語言及其編譯程序等的研究文獻不多，

也沒有實際的產(chǎn)品,我們對量子程序僅做簡單介經(jīng)。

按照較統(tǒng)一的認識量子程序的邏輯體系普通與經(jīng)典計算機類似，為便于控制

并使用通用量子計算機，必須通過量子計算機程序設計語言來描述待解問題，

因此，量子計算機程序設計語言將作為未來通用量子計算機上的一種重要系統(tǒng)

軟件?，F(xiàn)有量子算法普通固化于專用量子計算設備中，如果需要改變量子算法就

必須重新設計量子計算設備，實際匕這就相當干一臺求解特定具體問題不是

一類特定問題的專用計算設備。一方面，量子計算機程序設計語言的研究是為了

適應未來量子計算機的實際工作需要，另一方面，亦可有助于發(fā)現(xiàn)新的量子算

法并促進量子計算機的快速誕生。

量子程序設計語言近期發(fā)展趨勢可能是：

1）提高量子程序設計語言的級別

2）研究并發(fā)量子程序設計語言

3）著重研究語言的語義與語用

4）研究語言在現(xiàn)有量子設備上的實現(xiàn)。

國內(nèi)南京大學徐家福等在國外學者工作基礎之上提出一種基于Java語言擴展

而得的命令式量子程序設計語言NDDJava,并設計出其處理系統(tǒng)。通過在經(jīng)典計算

機上摹擬實現(xiàn)，正確運行了幾種量子算法，達到了預期效果。

四、科學的發(fā)展源于需求（量子計算機強大的功能）

1、P到NP

算法中的計算量，顧名思義，是指解決某問題所需要計算的時間。問題的計

算時間若以計算項數(shù)箱次上升的計算量完成，我們稱此問題為P-問題（P為英

文多項式Polynomial的第一字母），包含所有此類問題的集合以P表示。因此

P問題是一個凡能用0（n）計算量解決的問題的集合。NP是英文

nondeterministicpolynomial的縮寫，意思就是非確定性的多項式時間。大家

都猜測可能在P之外亦存在一類問題，其計算量是呈計算項數(shù)指數(shù)增加的，包

含所此類問題的集合以卡表示。NP中有一批互依的問題又稱之為

NP-complete類。1971年古克（StephenA.Cook）發(fā)表了（TheComplexityof

TheoremProvingProcedures〉論文把P之外的問題歸成為了三大類，即

NP,NP-complete以及NP-hard0對經(jīng)典計算機而言，一個呈鼎次上升的計算

量應該可以解決，但對一個呈指數(shù)上升的計算量在n相當大時則毫無希冀。

因此我們面臨的一個問題是在如何將一個呈指數(shù)上升的計算量問題，簡化成一

個累次上升的計算量問題。

經(jīng)典計算中存在著一大類NP問題。這種問題在經(jīng)典計算機上是不能計算的，

但是量子計算可以把其中的一部份NP問題變成P問題，即問題的復雜度隨著比特

位數(shù)的增長以多項式數(shù)量級上升。這種問題原則上是可以計算的。一個具體的例

子就是大因數(shù)分解，按經(jīng)典計算復雜性理論，這個問題不存在有效算法，所以被

利用來進行經(jīng)典密鑰分配。但是如果用量子計算機結合Shor量子算法，這個問題

就變成為了P問題。

例如，為了對一個400位的阿拉伯數(shù)字進行因子分解，目前最快的超級計算

機將耗時上百億年，這幾乎等于宇宙的整個壽命；而具有相同時鐘脈沖速度的量

子計算機只需要大約一分鐘。因此，對于目前的密碼系統(tǒng)，即使人們幾乎無法利

用經(jīng)典算法對其進行破解，但如果人們擁有了一臺量子計算機，那末目前的密碼

系統(tǒng)將毫無保密性可言！這一后果是對目前的密碼系統(tǒng)的巨大挑戰(zhàn)，于是對基于

經(jīng)典保密系統(tǒng)的行業(yè)（如軍事、國家安全、金融等）的信息安全構成根本的威脅。

Shor算法的核心是利用數(shù)論中的一些定理，將大數(shù)因子分解轉(zhuǎn)化為求某個

函數(shù)的周期。在量子計算機中Shor算法的每一步驟都是可以通過多項式