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

.----

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

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

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

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

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

獻(xiàn)論文和熟悉量子信息特殊是量子計(jì)算機(jī)的發(fā)展的基礎(chǔ)上我做了一

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

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

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

一、引言

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

向來閃爍著無限的光采。特別是近年來量子計(jì)算機(jī)、生物計(jì)算機(jī)、DNA計(jì)算等領(lǐng)

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

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

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

技的引領(lǐng)者？在閱讀一些文獻(xiàn)、論文和熟悉量子信息特殊是量子計(jì)算機(jī)的發(fā)展的

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

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

1、計(jì)算理論

1.1什么是計(jì)算

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

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

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

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

是計(jì)算了！因?yàn)槲覀儚氐卓梢园阉械淖匀唤绱嬖诘倪^程都抽象成這樣的輸入輸

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

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

子計(jì)算機(jī)這些新鮮玩藝！因?yàn)槿思野袲NA的化學(xué)反應(yīng)、量子世界的波函數(shù)變換都

看做是計(jì)算了，自然就會(huì)人為地把這些計(jì)算組合起來構(gòu)成計(jì)算機(jī)了。

1.2圖靈機(jī)

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

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

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

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

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

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

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

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

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

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

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

法過程都可以用圖靈機(jī)進(jìn)行有效摹擬。由于隨機(jī)算法的引入Church-Turing強(qiáng)論

題后來被修改為更強(qiáng)的論題:任何算法過程都可用概率圖靈機(jī)進(jìn)行有效摹擬。在

這個(gè)問題的啟示下，Deutsch與其他一些物理學(xué)家認(rèn)識(shí)到，一個(gè)數(shù)學(xué)問題的計(jì)算

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

使用的計(jì)算系統(tǒng)。正是這個(gè)認(rèn)識(shí)，使得量子計(jì)算的研究得到廣泛關(guān)注。隨后，

Deutsch提出是否可以用物理學(xué)定律推導(dǎo)出任何更強(qiáng)的Church-Turing論題的問

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

通用量子計(jì)算機(jī)的概念。

1.3量子圖靈機(jī)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如何在物理上構(gòu)造出量子計(jì)算機(jī)呢？

2、物理學(xué)基礎(chǔ)(量子力學(xué))

從物理觀點(diǎn)看，計(jì)算機(jī)是一個(gè)物理系統(tǒng)，計(jì)算過程是一個(gè)物理過程。量子計(jì)

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

化過程。量子力學(xué)中與量子計(jì)算關(guān)系最為密切的兩個(gè)特性是疊加態(tài)與糾纏態(tài)。由

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

算機(jī)的新特點(diǎn)。

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

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

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

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

可思議特性的重要物理基礎(chǔ)；

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

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

的狀態(tài)；

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

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

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

確的復(fù)制。量子不可克隆定理和測不許原理構(gòu)成量子密碼技術(shù)的物理基礎(chǔ)。

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

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

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

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

基于量子力學(xué)的相干特征，重構(gòu)信息密碼、信息計(jì)算和信息通訊的基本原理。

3、第一次的融合（量子計(jì)算機(jī)與可逆計(jì)算）

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

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

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

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

操作.例如，對兩比特的異或者操作，因?yàn)槲┆?dú)一比特的輸出，這一過程損失了

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

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

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

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

a十5

—@——a@b

0—7二@二b

圖1不可逆異或門改進(jìn)為可逆異或門

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

都可以改造為可逆計(jì)算機(jī)，而不影響其計(jì)算能力.因?yàn)橛?jì)算機(jī)中的每步操作都可

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

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

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

機(jī)的研究，其核心任務(wù)為，對應(yīng)于具體的計(jì)算，尋覓合適的哈密頓量來描述.早

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

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

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

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

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

子分解的量子多項(xiàng)式算法[81（見第三節(jié)），因?yàn)榇藛栴}在經(jīng)典公鑰體系中有重要

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

新月異.

此外值得指出的是計(jì)算與能量的關(guān)系。

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

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

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

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

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

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

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

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

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

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

行一個(gè)基本邏輯運(yùn)算約消耗能量月。若在計(jì)算中不存在信息擦除，則由定律知

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

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

逆計(jì)算的概念。

三、搶占量子計(jì)算機(jī)研制的高地

1、理論研究

理論上已證明量子圖靈機(jī)可以等價(jià)為一個(gè)量子邏輯電路，因此可以通過一些

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

比特、二比特、及三比特邏輯門等.因?yàn)榱孔舆壿嬮T是可逆的，所以其輸入和輸

出比特?cái)?shù)相等，量子邏輯門對輸入比特進(jìn)行一個(gè)確定的幺正變換，得到輸出比

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

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

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

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

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

合的一個(gè)稠密子集.實(shí)驗(yàn)上通常用一些具體的量工邏輯門來構(gòu)造計(jì)算機(jī)。Barenco

等人證明，一個(gè)二比特的異或者門和對一比特進(jìn)行任意操作的門可構(gòu)成一個(gè)通用

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

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

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

2.1基本要求

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

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

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

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

5）能夠測量量子位

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

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

2.2幾種方案

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

2）利用冷阱束縛離子

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

2.3量子計(jì)算的艱難及其克服途徑

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

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

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

子相干性的衰減）主要源于系統(tǒng)和外界環(huán)境的耦合.因?yàn)樵诹孔佑?jì)算機(jī)中，執(zhí)行

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

即導(dǎo)致消相干.Unni上定量分析了消相干效應(yīng)，結(jié)果表明，量子相干性的指數(shù)衰

減不可避免.Unruh的分析揭示了消相干的嚴(yán)重性，這一結(jié)果無疑是對量子計(jì)算

機(jī)的信奉者的當(dāng)頭一棒.

因?yàn)榱孔佑?jì)算機(jī)木質(zhì)性地利用了量子相干性，相干性的丟失就會(huì)導(dǎo)致運(yùn)算結(jié)

果出錯(cuò)，這就是量子錯(cuò)誤.除了消相干會(huì)不可避免地導(dǎo)致量子錯(cuò)誤外，其他一些

技術(shù)原因，例如量子門操作中的誤差等，也會(huì)導(dǎo)致量子錯(cuò)誤.因此，現(xiàn)在的關(guān)鍵

問題就變成，在門操作和量子存儲(chǔ)都有可能出錯(cuò)的前提下，如何進(jìn)行可靠的量子

運(yùn)算？

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

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

3、軟件

3.1量子算法

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

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

而測量時(shí)只能得到一個(gè)結(jié)果，而且不能選擇所需的結(jié)果。量子算法的中心思想是

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

樣客觀所需的結(jié)果在測量時(shí)就會(huì)以相當(dāng)高的概率浮現(xiàn)。

Geove算法

Shor算法

3.2量子計(jì)算機(jī)程序設(shè)計(jì)語言

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

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

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

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

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

并使用通用量子計(jì)算機(jī)，必須通過量子計(jì)算機(jī)程序設(shè)計(jì)語言來描述待解問題，

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

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

必須重新設(shè)計(jì)量子計(jì)算設(shè)備，實(shí)際匕這就相當(dāng)干一臺(tái)求解特定具體問題不是

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

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

法并促進(jìn)量子計(jì)算機(jī)的快速誕生。

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

1）提高量子程序設(shè)計(jì)語言的級(jí)別

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

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

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

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

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

機(jī)上摹擬實(shí)現(xiàn)，正確運(yùn)行了幾種量子算法，達(dá)到了預(yù)期效果。

四、科學(xué)的發(fā)展源于需求（量子計(jì)算機(jī)強(qiáng)大的功能）

1、P到NP

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

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

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

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

nondeterministicpolynomial的縮寫，意思就是非確定性的多項(xiàng)式時(shí)間。大家

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

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

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

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

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

量應(yīng)該可以解決，但對一個(gè)呈指數(shù)上升的計(jì)算量在n相當(dāng)大時(shí)則毫無希冀。

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

個(gè)累次上升的計(jì)算量問題。

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

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

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

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

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

就變成為了P問題。

例如，為了對一個(gè)400位的阿拉伯?dāng)?shù)字進(jìn)行因子分解，目前最快的超級(jí)計(jì)算

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

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

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

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

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

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

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