陳靈生

浙江廣電集團，浙江 杭州 310005

1 經(jīng)典計算機與Moore定律

所謂經(jīng)典計算機就是指目前在廣泛使用的電子計算機，之所以稱為經(jīng)典計算機，是因為現(xiàn)在有了量子計算機的概念。毫無疑問，經(jīng)典計算機在廣泛的使用領(lǐng)域取得了巨大的成功，很難想象那個行業(yè)能離得開計算機。

電子計算機的發(fā)展依賴于大規(guī)模集成電路技術(shù)的發(fā)展。早在1965年，Moore就提出大膽預(yù)言（后來該預(yù)言被稱為Moore定律）:在未來十年內(nèi)集成到一個芯片內(nèi)的晶體管數(shù)目每一年（后來修正為每18個月）翻一番。該定律居然神奇地有效了40多年。雖然Intel等公司還在極力維持Moore定律的有效性[1]，但是這種趨勢不可能無限地延續(xù)下去，因為隨著集成度的不斷加大，設(shè)計一個存儲單元的原子數(shù)目將達到幾個原子的數(shù)量級。一旦只涉及幾個原子和電子，經(jīng)典物理學(xué)規(guī)律將不再有效，必須要用量子物理學(xué)來處理，因此量子計算機的出現(xiàn)可以說是科學(xué)技術(shù)發(fā)展的必然結(jié)果。

2 量子計算機概念的提出

計算機是執(zhí)行計算任務(wù)的機器，它的本質(zhì)是一個物理系統(tǒng)，計算過程本質(zhì)上是個物理過程，量子計算機在本質(zhì)上就是一個量子力學(xué)系統(tǒng)[2]。

美國物理學(xué)家Feynman在1982年提出量子計算的概念。在更早一點的時候，Benioff在“作為物理系統(tǒng)的計算機”一文中證明了一個重要的定理[3]，從該定理得出的結(jié)論是，通過量子態(tài)的幺正演化可以實現(xiàn)經(jīng)典圖靈機得計算功能。因此量子計算機所理論上是可行的，而且它的性能至少不低于經(jīng)典計算機。

由于量子態(tài)的幺正演化只存在于理想的孤立系統(tǒng)中，但在實際中，量子系統(tǒng)不可避免地和周圍環(huán)境發(fā)生相互作用，表現(xiàn)為量子計算中的噪聲干擾，導(dǎo)致量子計算很容易出錯。同時人們也不清楚，量子計算是否優(yōu)于經(jīng)典計算，所以量子計算一開始只停留在理論上可行的階段。

3 量子計算

隨著一些優(yōu)秀的量子算法被人們陸續(xù)發(fā)現(xiàn)，量子計算機逐漸成為研究的熱點。特別是美國計算機專家Shor于1994年提出的大數(shù)的素因子分解算法特別引人注目。大數(shù)素因子分解算法之所以重要，是因為大數(shù)的素因子分解是經(jīng)典計算機的難解問題，而這正是目前廣泛使用的RSA公開密鑰加密系統(tǒng)得以安全的先決條件的。也就是說大數(shù)的因子分解是經(jīng)典計算理論中的NP難題，然而Shor的量子算法把它轉(zhuǎn)化為P類問題。這給量子計算機研究注入了新的活力，引發(fā)了量子計算機研究的熱潮[4]。

量子計算機之所以有可能取得遠超經(jīng)典計算機的計算性能，是和量子計算本身的特點分不開的。經(jīng)典計算處理的基本單元是比特（bit，即二進制的0或1），與之對應(yīng)，量子計算處理的單元是量子比特（quantum bit，qubit）。量子比特通常用Dirac標記寫成和的形式，也稱為計算基矢，它們相互正交。經(jīng)典比特要么處于0，要么處于1；但量子比特則不同，它不僅可以是或，而且可以是這兩種態(tài)的任意線性組合

其中α和β是復(fù)系數(shù)，滿足歸一化條件

這就是量子態(tài)的疊加原理。

量子態(tài)疊加原理是量子計算機有可能進行大規(guī)模并行計算的物理基礎(chǔ)。單個量子比特可以處于疊加態(tài)，多個量子比特組成的量子系統(tǒng)也可以處于疊加態(tài)。而且量子系統(tǒng)的態(tài)空間的維數(shù)隨著量子比特數(shù)的增加成指數(shù)上升。比如兩個量子比特組成的量子系統(tǒng)，它的基矢有，該系統(tǒng)可以處在這四個態(tài)的疊加態(tài)中。一般地，n個量子比特系統(tǒng)的態(tài)空間是2n維Hilbert空間，可以用它的2n各基矢（其中i是個n位二進制數(shù)串），制備出一般態(tài):

如果量子計算機對2n這個一般態(tài)進行計算，就相當于對個基矢態(tài)同時進行計算，這就是量子計算的并行性。

與經(jīng)典計算機中的邏輯門相對應(yīng)，量子信息處理的基本操作元件是量子邏輯門。從數(shù)學(xué)的觀點看，量子邏輯門就是幺正矩陣或是幺正矩陣的組合，對量子態(tài)實施幺正變換就實現(xiàn)了對量子態(tài)所表達的數(shù)據(jù)的計算。

如果對任意維的Hilbert空間態(tài)（即量子態(tài)）的幺正變換，都可以通過一個邏輯門的組合來實現(xiàn)，那么這個邏輯門就是一個通用邏輯門。對于量子計算的通用邏輯門組，就是所謂的Deutsch門。Deutsch證明任意維Hilbert空間的幺正變換的量子計算網(wǎng)絡(luò)都可以用這個門的組合構(gòu)造出來。這樣從理論上來說，可以像用經(jīng)典邏輯門構(gòu)建經(jīng)典計算機一樣，用量子邏輯門構(gòu)建量子計算機。

量子計算中還可利用的一個資源就是所謂的量子糾纏。比如雙量子比特系統(tǒng)處于態(tài)

這就是一個糾纏態(tài)。在這個特殊的態(tài)中，復(fù)合系統(tǒng)（雙量子比特）的態(tài)是完全確定的，但其中每個子系統(tǒng)（單個量子比特）的態(tài)是不確定的。同時兩個子系統(tǒng)之間存在著不可分割的聯(lián)系，表現(xiàn)為對其中任何一個子系統(tǒng)的測量會引起另一個子系統(tǒng)態(tài)的瞬時改變，不管兩個子系統(tǒng)相距有多遠。目前，人們可以利用量子糾纏實現(xiàn)隱形傳態(tài)，即利用兩地共享的量子糾纏對，把其中一地的未知量子態(tài)傳輸?shù)搅硪坏?，卻不需要傳送這個量子比特本身。還可以利用量子糾纏實現(xiàn)超密編碼，即用一個量子比特位傳送兩個比特的經(jīng)典信息。

4 量子計算機的實現(xiàn)與挑戰(zhàn)

經(jīng)典計算機的實現(xiàn)方法比較統(tǒng)一，都是以大規(guī)模集成電路為基礎(chǔ)，采用Von Neumann的體系結(jié)構(gòu)。然而，目前提出的量子計算機的實現(xiàn)方法則五花八門，不同學(xué)科的研究人員都從自己的研究領(lǐng)域出發(fā)，提出不同的實現(xiàn)方法。從理論上說，只要滿足量子計算所需的條件，任何實現(xiàn)方法都是可行的。目前已經(jīng)提出的量子計算機的物理實現(xiàn)方案有:核磁共振量子計算機、離子阱量子計算機、中性原子量子計算機、光量子量子計算機、超導(dǎo)量子計算機等[2]。

雖然量子計算機和量子算法已經(jīng)有了基本框架，但最終要實現(xiàn)具有實用價值的量子計算機，還存在著許多需要解決的問題。對于這么多種量子計算機的實現(xiàn)方案，哪一種最具實現(xiàn)價值，還沒有定論。

同時，量子計算機的性能到底能比經(jīng)典計算機優(yōu)越多少，也不是十分清楚。雖然由于量子態(tài)的疊加性，量子計算可以實現(xiàn)大規(guī)模的并行運算，但一旦要讓計算結(jié)果輸出，必須進行測量，一旦進行測量，疊加態(tài)就會坍縮到被測物理量的一個本征態(tài)。因此要通過測量把并行計算的所有結(jié)果都讀出來是不可能的。如何利用量子計算中的并行特性，需要巧妙的算法設(shè)計。因此到目前為止，除了Shor大數(shù)素因子分解算法、Grover數(shù)據(jù)庫搜索算法等少數(shù)幾個優(yōu)秀的量子算法之外，再尋找優(yōu)秀量子算法的難道很大。量子計算機要真正進入實用還有很長的路要走。

[1]張邦維.Moore定律還會繼續(xù)有效嗎[J].自然雜志，2004，26(1).

[2]李承祖，陳平形，梁林梅，戴宏毅.量子計算機研究(上):原理和物理實現(xiàn)[M].科學(xué)出版社，2011.

[3]P.Beniof f.The computer as a physical system:A microscopic quantum mechanical Hami ltonian model of computers as represented by Turing machines.Journal of Statistical Physics, 1980，22.

[4]趙生妹，鄭寶玉.量子信息處理技術(shù)[M].北京郵電大學(xué)出版社，2010.