量子計(jì)算機(jī)理論概述

陳靈生

浙江廣電集團(tuán)，浙江 杭州 310005

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

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

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

2 量子計(jì)算機(jī)概念的提出

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

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

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

3 量子計(jì)算

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

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

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

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

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

如果量子計(jì)算機(jī)對(duì)2n這個(gè)一般態(tài)進(jìn)行計(jì)算，就相當(dāng)于對(duì)個(gè)基矢態(tài)同時(shí)進(jìn)行計(jì)算，這就是量子計(jì)算的并行性。

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

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

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

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

4 量子計(jì)算機(jī)的實(shí)現(xiàn)與挑戰(zhàn)

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

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

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

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

[2]李承祖，陳平形，梁林梅，戴宏毅.量子計(jì)算機(jī)研究(上):原理和物理實(shí)現(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.