量子信息基礎(chǔ)與量子算法

1、專題報(bào)道Cover Features Communications of CCF 2008/7 14量子信息基礎(chǔ)與量子算法龍桂魯引言量子信息學(xué)是涉及量子力學(xué)、信息論、計(jì)算機(jī)科學(xué)的交叉學(xué)科，誕生于20世紀(jì)70年代末，在20世紀(jì)90年代中期得到迅速發(fā)展。量子信息學(xué)的研究內(nèi)容包括量子計(jì)算、量子通信。本文主要介紹量子信息學(xué)基礎(chǔ)、量子力學(xué)基礎(chǔ)、量子通信以及幾種典型的量子算法。量子計(jì)算機(jī)這個(gè)現(xiàn)在經(jīng)常被人提起的名詞誕生在18年前。它是沿著兩條不同的發(fā)展路線發(fā)展的：一條路線是可逆計(jì)算機(jī)，可以極大地減少量子計(jì)算機(jī)熱耗。貝尼奧夫（Benioff ）首先利用量子力學(xué)理論構(gòu)造了這種量子計(jì)算機(jī)1；另一條路線是需求（對(duì)量

2、子體系模擬的需求），費(fèi)曼（Feynman ）指出，對(duì)一個(gè)量子力學(xué)體系進(jìn)行模擬，所需的計(jì)算量與體系大小成指數(shù)函數(shù)關(guān)系，經(jīng)典計(jì)算機(jī)是無法滿足模擬需要。對(duì)量子體系的模擬，必須使用以量子迭加態(tài)進(jìn)行計(jì)算的量子計(jì)算機(jī)2。早期對(duì)量子計(jì)算機(jī)的研究非常少，全世界大約只有10位科學(xué)家涉獵此類工作。1995年，肖爾（Shor ）構(gòu)造了大數(shù)質(zhì)因子分解的量子算法3，顯示出量子計(jì)算機(jī)超越經(jīng)典計(jì)算機(jī)的強(qiáng)大潛能，引起了美國國防和安全部門的重視。這極大地推動(dòng)了量子計(jì)算機(jī)研究，使量子計(jì)算機(jī)成為學(xué)術(shù)研究前沿和戰(zhàn)略目標(biāo)。大約在量子計(jì)算機(jī)提出的同一時(shí)期，威斯納（Wiesner ）提出了利用量子力學(xué)制備不可復(fù)制的鈔票的方案，但是因?yàn)檫^于

3、超前和脫離現(xiàn)實(shí)，被審稿人否定。1984年，班內(nèi)特（Bennett ）和布拉薩德（Brassard ）兩人將威斯納的思想用于通信4，證明量子力學(xué)原理可以保證通信的安全性，從此誕生了量子通信。1992年，班內(nèi)特等6人一起提出了一個(gè)量子通信方案：利用量子糾纏，不需要傳遞實(shí)物粒子就可以把一個(gè)量子物體的狀態(tài)轉(zhuǎn)移到遙遠(yuǎn)地方的另一個(gè)粒子上，這就是量子隱形傳態(tài)5。本文著重介紹基礎(chǔ)性知識(shí)和一些新的發(fā)展方向，如需要比較詳細(xì)系統(tǒng)的閱讀，請參考文獻(xiàn)6,7。一些新的進(jìn)展請參考文獻(xiàn)8-11。量子力學(xué)簡介量子力學(xué)基本假設(shè)有關(guān)量子力學(xué)的教科書請參閱文獻(xiàn)12-14。量子力學(xué)有五個(gè)基本假設(shè)：1量子系統(tǒng)的狀態(tài)可以用希爾伯特（Hil

4、bert ）空間中的態(tài)矢量 來描述。2量子系統(tǒng)的所有力學(xué)量都對(duì)應(yīng)希爾伯特空間中的線性厄米算符或厄米矩陣。3對(duì)處在狀態(tài) 的量子力學(xué)體系測量力學(xué)量 ，測量得到的結(jié)果只能是算符 的本征值，測得本征值 的概率正比于 測量之后的瞬間，體系的波函數(shù)突變到測得的本征值 所對(duì)應(yīng)的本征函數(shù) 上。測量帶來的波函數(shù)突變叫做波函數(shù)的塌縮，又叫做馮諾依曼（Von Neumann ）約化（Reduction ）。4孤立量子系統(tǒng)的態(tài)矢量 隨時(shí)間演化遵從薛定諤（Schrödinger）方程：Communications of CCF 2008/7 15， （1）其中 是系統(tǒng)的哈密頓量。5描述全同粒子系統(tǒng)的態(tài)矢量，對(duì)

5、于任意一對(duì)粒子進(jìn)行交換，是對(duì)稱或反對(duì)稱的。服從前者的粒子稱為玻色子，服從后者的粒子稱為費(fèi)米子。量子態(tài)迭加原理如果 是量子系統(tǒng)所有可能的態(tài)，那么它們的任意線性迭加態(tài)（2）仍然是此量子系統(tǒng)的一個(gè)可能的態(tài)。量子態(tài)迭加原理與經(jīng)典的態(tài)迭加原理的本質(zhì)區(qū)別體現(xiàn)在測量上。對(duì)經(jīng)典物理的迭加態(tài)進(jìn)行測量，我們得到的結(jié)果是處在迭加態(tài)中各個(gè)子態(tài)的中間情況。例如測量經(jīng)典的自旋為1/2的粒子的自旋向上和向下的態(tài)的等幅迭加態(tài)的自旋第三分量，我們得到為零。而對(duì)于處在量子力學(xué)迭加態(tài)的粒子做同樣的測量，我們只能得到向上或者向下的結(jié)果，不可能得到自旋為零的結(jié)果。經(jīng)典物理中的迭加是幾率的迭加，而量子物理中的迭加是幾率幅的迭加，是同一個(gè)

6、量子體系各個(gè)可能狀態(tài)的線性迭加，迭加后的態(tài)是此量子體系的一個(gè)新態(tài)，具有新的特性。測不準(zhǔn)原理簡單地說，不可能對(duì)一個(gè)物理體系同時(shí)測準(zhǔn)兩個(gè)不相容的物理量。不相容的物理量是不對(duì)移的。例如，坐標(biāo)和動(dòng)量就是一對(duì)不相容的物理量，不可能同時(shí)測準(zhǔn)微觀粒子的位置和動(dòng)量，它們的不確定性滿足。密度算符和約化密度矩陣如果一個(gè)量子力學(xué)體系能夠用一個(gè)波函數(shù)來描述，我們稱它處在一個(gè)純態(tài)上；否則，我們稱它處在一個(gè)混合態(tài)上。處在混合態(tài)上的粒子以一定的概率出現(xiàn)某個(gè)波函數(shù)上。通常有三種情況可以用密度矩陣或者混合態(tài)來描述一個(gè)量子力學(xué)體系的狀態(tài)。有關(guān)密度矩陣可參考文獻(xiàn)15。第一種情況，假設(shè)有一個(gè)由N 個(gè)量子力學(xué)體系組成的系統(tǒng)，為了簡便，

7、將每個(gè)這樣的量子力學(xué)體系稱為一個(gè)分子。這些分子之間是獨(dú)立的、沒有相互作用的。有 個(gè)粒子處在態(tài) 上，共有k 種波函數(shù)， 。對(duì)于這樣的一個(gè)大系統(tǒng)，如果隨機(jī)地從里面取出一個(gè)分子，那么這個(gè)分子就有 的幾率處在態(tài)上。這個(gè)大系統(tǒng)中的分子的平均狀態(tài)可以寫成第二種情況是對(duì)于復(fù)雜的耦合系統(tǒng)。如果只注意其中的一部分子系統(tǒng)的時(shí)候，就無法用態(tài)矢量來描述系統(tǒng)的全部信息。在這種情況下也引入密度算符來描述量子系統(tǒng)及其演化。 例如對(duì)于兩個(gè)粒子A 和B 組成的復(fù)合系統(tǒng)，它的狀態(tài)可以寫成 。相應(yīng)的密度算 符就是 如果只考慮其中的A 粒子，則其狀態(tài)可以 用以下密度矩陣表示（6）其中 是求跡，是對(duì)B 粒子狀態(tài)求平均。第三種可以有混合

8、態(tài)的情況是，假設(shè)一個(gè)量子體系處在一個(gè)多變的環(huán)境，如果不關(guān)心它的瞬時(shí)狀態(tài)，只想知道它在一段時(shí)間內(nèi)的平均狀態(tài)，此時(shí)可以對(duì)它進(jìn)行時(shí)間的平均，從而得到混合態(tài)。這種情況與第一種情況類似，是將第一種情況的對(duì)空間平均換成了對(duì)時(shí)間的平均。量子信息的理論基礎(chǔ)非克隆定理非克隆定理16的內(nèi)容為：一個(gè)未知的量（3）（4）（5）( 為普郎克常數(shù)專題報(bào)道Cover Features Communications of CCF 2008/7 16子態(tài)不能被完全拷貝。雖然量子態(tài)不能精確克隆，但是可以近似克隆，或者可以進(jìn)行概率地精確克隆17。量子幺正操作和量子邏輯門根據(jù)量子力學(xué)理論，孤立量子系統(tǒng)態(tài)矢量隨時(shí)間的動(dòng)力學(xué)演化遵從薛定

9、諤方程（7）幺正算符 對(duì)應(yīng)的變化通常被稱為幺正變換或幺正操作。演化算符的幺正性使得量子信息過程有一些特殊的性質(zhì)：（1）保幾率性，即量子態(tài)的歸一化性質(zhì)不隨時(shí)間的改變而改變，量子系統(tǒng)的總幾率保持不變；（2）可逆性，即量子信息處理中的所有邏輯操作都是可逆的。在量子信息處理過程中，系統(tǒng)的幺正演化通過量子邏輯門來完成，根據(jù)作用的量子位數(shù)目，量子邏輯門被分為單量子比特門、二量子比特門和多量子比特門。常見的單比特量子門主要有 和沃爾什-哈德曼（Walsh-Hadamard ）門H 。量子受控非門（C N O T 門）是最常用的二比特量子門之一，其中的兩個(gè)量子比特分別為控制比特與目標(biāo)比特。當(dāng)控制比特為時(shí)，它不

10、改變目標(biāo)位；當(dāng)控制比特為時(shí)，它將翻轉(zhuǎn)目標(biāo)位。量子糾纏態(tài)和貝爾不等式理論量子糾纏態(tài)的定義是：對(duì)于兩粒子系統(tǒng)A 和B ，如果存在態(tài) 和 使得兩粒子系統(tǒng)的量子態(tài)可以寫成直積形式 ，則稱此量子系統(tǒng)處于直積態(tài)（product state ）；否則，稱此量子系統(tǒng)處于糾纏態(tài)（entangled state ）。伯姆（Bohm ）針對(duì)自旋為1/2的二能級(jí)量子體系提出了簡化的糾纏態(tài)形式18，稱之為貝爾（Bell ）基態(tài)，其中 和 分別表示二能級(jí)體系的2個(gè)本征態(tài)。經(jīng)研究發(fā)現(xiàn)，貝爾基態(tài)是兩粒子系統(tǒng)的最大糾纏態(tài)。對(duì)于三粒子的情況，格林伯格（Greenberger ）、霍姆（Horne ）和澤林格（Zeilinger

11、）三人給出了三體最大糾纏態(tài)的形式19，稱為GHZ 態(tài)，（9）1964年，貝爾從隱變量和定域?qū)嵲谡摮霭l(fā)，導(dǎo)出了一個(gè)不等式來判斷量子力學(xué)還是隱變量理論正確20。利用貝爾不等式可以在實(shí)驗(yàn)上檢驗(yàn)定域性，（10）其中 是對(duì)A 、B 粒子在 方向上進(jìn)行測量得到的測量結(jié)果的關(guān)聯(lián)函數(shù)，隱變量理論滿足上式，而量子力學(xué)中有些狀態(tài)不滿足，考慮兩粒子糾纏態(tài)（11） 就破壞貝爾不等式。貝爾不等式后來被推廣為多種形式。1969年，克勞澤（Clauser ）、霍姆、奚模尼（Shimony ）和霍爾特（Holt ）提出了CHSH 不等式21，在這之后，各種貝爾型定理相繼被提出，為研究量子力學(xué)和定域?qū)嵲谛灾g的矛盾提供了場所。

12、1982年阿斯佩克（A s p e c t ）等人進(jìn)行了貝爾定理的驗(yàn)證實(shí)驗(yàn)22。實(shí)驗(yàn)結(jié)果與量（8）（12）Communications of CCF 2008/7 17子力學(xué)符合，從而驗(yàn)證了糾纏粒子對(duì)違背了貝爾不等式，量子力學(xué)是非定域的。雖然現(xiàn)在大多數(shù)人相信量子力學(xué)是正確的，但是現(xiàn)有的實(shí)驗(yàn)還有缺陷，還不能完全說服反對(duì)者。量子糾纏的非局域性沒有經(jīng)典的類比現(xiàn)象，如何理解量子糾纏一直是爭論的熱點(diǎn)。目前研究一個(gè)量子態(tài)是否糾纏，以及如何判斷量子糾纏的大小是量子信息的基礎(chǔ)理論研究中的重要研究方向23。實(shí)驗(yàn)上已經(jīng)實(shí)現(xiàn)了多個(gè)光子的糾纏態(tài)25和在任何自由度上都糾纏的超糾纏光子對(duì)26。量子通信簡單地說，量子通信就

13、是通過量子信道實(shí)現(xiàn)經(jīng)典信息或者量子狀態(tài)的傳輸。按照這種定義量子隱形傳態(tài)、密集編碼等都屬于量子通信。有的作者將量子密鑰分配叫做量子通信，讀者在閱讀時(shí)需要注意。量子隱形傳態(tài)量子隱形傳態(tài)是根據(jù)英文Q u a n t u m Teleportation 翻譯來的，也可譯成“量子離物傳態(tài)”。它的實(shí)質(zhì)是利用量子糾纏，使得一個(gè)粒子在A 處的狀態(tài)消失，而在另外一個(gè)地點(diǎn)B 處出現(xiàn)。量子隱形傳態(tài)沒有經(jīng)典對(duì)應(yīng)模式，是量子力學(xué)特有的。它是班內(nèi)特等六個(gè)人在1993年提出的5，有的作者把這個(gè)最初方案就做六人方案，其原理如圖1所示。手中有一個(gè)粒子，愛麗絲不知道它的量子狀態(tài)。要求愛麗絲不實(shí)際發(fā)送手中的粒子，把它的狀態(tài)傳送給遠(yuǎn)

14、處的鮑勃。量子隱形傳態(tài)過程可以摘述如下：假設(shè)愛麗絲手中的未知量子態(tài)為其中 。為了完成未知量子態(tài)的傳輸，愛麗絲和鮑勃先共享一對(duì)狀態(tài)為 的EPR 1對(duì)，并分別擁有糾纏對(duì) 中的2和3粒子。然后，愛麗絲對(duì)未知態(tài)粒子A 和粒子2做聯(lián)合貝爾基測量，此過程是一個(gè)重糾纏的過程。此時(shí)，愛麗絲將以相等的概率測量得到4個(gè)貝爾基態(tài)，得到每個(gè)貝爾基態(tài)的幾率各占1/4。當(dāng)愛麗絲完成貝爾基測量后，鮑勃手中的粒子3就會(huì)塌縮到對(duì)應(yīng)的量子態(tài)。此時(shí)，愛麗絲告訴鮑勃她得到的測量結(jié)果，鮑勃可以通過選擇適當(dāng)?shù)溺壅僮鱽韺⒘Ｗ?的量子態(tài)轉(zhuǎn)換到愛麗絲原來的未知量子態(tài)，即恢復(fù)到量子態(tài) ，從而實(shí)現(xiàn)未知量子態(tài)的離物傳輸。雖然在愛麗絲做測量時(shí)狀態(tài)的

15、塌縮是瞬時(shí)發(fā)生的，但是這里并不能實(shí)現(xiàn)超光速通信。因?yàn)橹挥辛孔討B(tài)的塌縮并不能夠?qū)崿F(xiàn)信息的傳輸，鮑勃只有在得到了愛麗絲的測量結(jié)果之后才能實(shí)現(xiàn)粒子狀態(tài)的轉(zhuǎn)移。而愛麗絲的測量結(jié)果需要通過經(jīng)典通信傳輸，因此不可能進(jìn)行超光速通信。最近發(fā)展的受控量子隱形傳態(tài)，在量子保密通信上具有重要的應(yīng)用27。量子糾纏轉(zhuǎn)移量子糾纏轉(zhuǎn)移也是在1993年提出的28。其原理如圖2所示。假設(shè)粒子l 和k 處在糾纏態(tài)，粒子m 和n 也處在糾纏態(tài)上。糾纏態(tài)有一個(gè)特性，即使它們離開很遠(yuǎn)，它們之間的糾纏狀態(tài)也能保持。如果將粒子k 和粒子m 放在一起并進(jìn)行貝爾基的測量。測量之后這4個(gè)粒子組成的體系的波函數(shù)就會(huì)發(fā)生塌縮。塌縮之后，粒子l 和n

16、 就會(huì)產(chǎn)生糾纏，而此前它們之間是沒有 糾纏的。圖1 量子隱形傳態(tài)原理圖在量子隱形傳態(tài)中，通信雙方愛麗絲（Alice ）和鮑勃（Bob ）的任務(wù)是：愛麗絲專題報(bào)道Cover Features Communications of CCF 2008/7 1量子中繼就是利用了量子糾纏轉(zhuǎn)移。假設(shè)有三個(gè)地點(diǎn)A 、B 和C ，B 點(diǎn)在中間。如果A 和B 之間有量子糾纏態(tài)，B 和C 之間有量子糾纏態(tài)，通過量子糾纏轉(zhuǎn)移就可以實(shí)現(xiàn)A 和C 之間的量子糾纏。依次類推，可以實(shí)現(xiàn)任意長距離的粒子之間的量子糾纏，從而實(shí)現(xiàn)量子中繼。量子密集編碼量子密集編碼是指利用量子糾纏，雖然只傳送1個(gè)比特，但是卻傳送了2個(gè)比特的信息的一

17、種量子通信。它是1992年由班內(nèi)特和威斯納提出的29，其原理如圖3所示。它的過程是：在通信前，接收者鮑勃將量子態(tài)制備在貝爾基態(tài)上。鮑勃保留粒子B ，并將粒子A 發(fā)給愛麗絲，此時(shí)，鮑勃和愛麗絲之間就共享了一對(duì)糾纏粒子對(duì)愛麗絲接收到粒子A 后，選擇4個(gè)幺正操作 和 來改變由A 和B 粒子組成的量子系統(tǒng)的量子態(tài)。然后，愛麗絲將粒子A 再發(fā)送給鮑勃，鮑勃對(duì)AB 粒子做聯(lián)合貝爾基測量，從而得到愛麗絲所做的幺正操作信息。這樣鮑勃就通過一個(gè)粒子的傳輸而傳送了4個(gè)量子操作的信息。如果通信雙方事先約定量子操作 和 分別代表編碼00、01、10和11，那么愛麗絲和鮑勃之間通過1個(gè)粒子的交換，完成了2比特經(jīng)典信息的

18、傳輸，這就是量子密集編碼。量子密集編碼是量子信息的研究熱點(diǎn)之一，例如向高維、多方的方向發(fā)展30，向?qū)ΨQ的方向的發(fā)展31，并且在核磁共振和光學(xué)量子體系進(jìn)行了實(shí)驗(yàn)演示32-35。量子密鑰分配自從班內(nèi)特和布拉薩德在1984年提出第一個(gè)量子密碼協(xié)議（BB84協(xié)議）4以來，量子密碼理論研究得到了很大發(fā)展，許多的量子密碼協(xié)議被提出。與傳統(tǒng)密碼學(xué)不同，量子密鑰分配（Quantum Key Distribution ，QKD ）是密碼學(xué)與量子力學(xué)結(jié)合的產(chǎn)物，它以量子態(tài)為信息載體，利用量子力學(xué)的基本原理來保護(hù)信息并通過量子信道傳送，在彼此之間建立共享密鑰。這種方法也稱為量子密碼通信。其安全性是由量子力學(xué)中的測不

19、準(zhǔn)原理和非克隆定理來保證的。量子密鑰分配不是用于傳輸密文，而是用于建立、傳輸密碼本，即在保密通信雙方分配密鑰。到目前，可以說量子密鑰分配是量子通信技術(shù)里最成熟的分支之一，這不僅體現(xiàn)在理論上提出了數(shù)十種密鑰分配方案，而且在實(shí)驗(yàn)上也取得了突出的進(jìn)展。在量子密鑰分配中，不同的信號(hào)源將依賴不同的量子特性和量子原理來保證通信的安全性。因此，我們可以根據(jù)信號(hào)源的不同將量子密鑰分配大體上分為三類：（1）基于單粒子系統(tǒng)量子特性的量子密鑰分配方案，如BB84協(xié)議4、B92協(xié)議36和HKH98協(xié)議37等；（2）基于糾纏粒子系統(tǒng)的量子關(guān)聯(lián)性和非定域性等量子特性的量子密鑰分配方案，例如Ekert91協(xié)議38、BBM9

20、2協(xié)議39圖2量子糾纏轉(zhuǎn)移原理圖圖3 量子密集編碼原理圖。Communications of CCF 2008/7 1和Long-Liu2002協(xié)議40等；（3）基于糾纏粒子與單粒子混合系統(tǒng)的量子密鑰分配方案，例如卡貝略. 霍爾夫（C a b e l l o-H o l e v o ）協(xié)議41和薛-李-郭（Xue-Li-Guo ，音譯）2002協(xié)議42等。我們說量子密鑰分配是安全的，并不是說竊聽者不能竊聽量子信道，而是通信雙方通過對(duì)一定的抽樣數(shù)據(jù)出錯(cuò)率e 的分析，能夠判斷是否有人竊聽量子信道。從而判斷在雙方傳輸?shù)牧孔颖忍厥欠窨捎?。量子直接安全通信量子直接安全通信利用量子態(tài)來直接傳輸機(jī)密信息本身

21、40,43,44。量子直接安全通信能夠大大提高量子通信的效率。隨著量子技術(shù)應(yīng)用的發(fā)展，量子直接安全通信會(huì)有越來越多的應(yīng)用。量子密鑰分發(fā)是在兩個(gè)相距很遠(yuǎn)的用戶之間建立共同的密鑰。量子密鑰分配的安全性要求通信的雙方能夠探測到竊聽者，并且在誤碼率較小的時(shí)候通過糾錯(cuò)和秘密放大得到任意程度的安全密鑰。得到了共同的密鑰之后，一方通過某種經(jīng)典加密手段，如一次一密方法，將信息（plaintext ）加密得到密文（ciphertext ），再通過經(jīng)典通道將密文發(fā)送給另外一方。在量子直接安全通信中，在量子信道中直接傳輸信息，不需要將信息加密成為密文通過經(jīng)典信道傳輸。因而，量子直接安全通信具有比量子密鑰分配更加嚴(yán)格

22、的要求。通信雙方除了能夠探測到竊聽者之外，還需要保證在發(fā)現(xiàn)竊聽者之前所傳遞的信息不泄露。研究表明，要達(dá)到這樣的安全性，必須在通信的時(shí)候使用塊傳輸，即將一定數(shù)量的量子信息的載體成批地由一方傳遞到另外一方。近年來量子直接安全通信成為大家關(guān)注的研究熱點(diǎn)，眾多的量子直接安全通信理論方案被提出，既有使用糾纏量子態(tài)的，也有使用單光子態(tài)的。但是，量子態(tài)在實(shí)際量子信道的傳輸過程中必然會(huì)受到噪聲的影響，這是任何量子通信都必將面臨的問題。在量子密碼通信中，因噪聲的影響而可能泄漏的信息可以通過經(jīng)典的秘密放大處理方法來降低。這種處理雖然導(dǎo)致密碼傳輸比特率降低，但可以把泄漏的信息減少到任意小的程度。但是在量子安全直接通

23、信中這一個(gè)問題并不好解決，特別是基于單光子雙向運(yùn)動(dòng)的物理模型。為了降低噪聲的影響，需要對(duì)量子態(tài)做純化處理。因此量子直接通信的安全性分析，可允許的誤碼率等是量子直接安全通信的關(guān)鍵。由于在量子直接安全通信中需要塊傳輸，因此要求通信的一方具有量子態(tài)存儲(chǔ)設(shè)備，而這一設(shè)備也是長距離量子通信和量子計(jì)算所需要的。這也是量子直接安全通信技術(shù)的關(guān)鍵。量子直接安全通信的實(shí)驗(yàn)研究和實(shí)用化是另一個(gè)重要的關(guān)鍵。量子算法量子計(jì)算機(jī)是服從量子力學(xué)規(guī)律的新型計(jì)算模型。通常需要用量子計(jì)算機(jī)模擬量子物理系統(tǒng)隨時(shí)間的演化從而完成某一計(jì)算任務(wù)，這就需要給出具體的算法，即給出量子邏輯門序列來實(shí)現(xiàn)這個(gè)幺正操作。量子算法的目的是將一系列量

24、子邏輯門組織起來，實(shí)現(xiàn)對(duì)量子計(jì)算機(jī)狀態(tài)的幺正操作，使量子計(jì)算機(jī)按照設(shè)計(jì)者的意愿隨時(shí)間演化，達(dá)到預(yù)期的輸出狀態(tài)。量子并行性量子并行計(jì)算貫穿于量子算法之中，使得量子算法與經(jīng)典算法相比，以更高的效率得到所期望的計(jì)算結(jié)果。量子并行性是指：如果將量子計(jì)算過程中實(shí)施某個(gè)函數(shù) 的幺正操作 作用在量子寄存器的輸入迭加態(tài)上，則它將對(duì)每個(gè)基矢量進(jìn)行作用后并將所有結(jié)果進(jìn)行線性迭加，產(chǎn)生一個(gè)輸出迭加態(tài)。因此，只需要應(yīng)用一次 就可以同時(shí)計(jì)算出不同 值對(duì)應(yīng)的函數(shù) 。1 由愛因斯坦波道爾斯基羅森（EinsteinPodolskyRosen）首先提出的概念，即總自旋為零 的粒子對(duì)。專題報(bào)道Cover Features Com

25、munications of CCF 2008/720 （13）當(dāng)前量子算法的基本思想主要有兩種：（1）對(duì)振幅的放大，即放大所需要的輸出值的振幅。其基本思想是對(duì)量子態(tài)進(jìn)行幺正變換，從而放大所需要的輸出值，使得在測量的時(shí)候可以較大的概率得到該結(jié)果，例如，格洛弗（G r o v e r ）算子搜索算法及其推廣算法45-47。（2）相位估計(jì)算法。這類算法通過對(duì)相位進(jìn)行操作，從而得到所需要的結(jié)果，例如，肖爾大數(shù)質(zhì)因子分解算法3。目前，根據(jù)量子算法對(duì)計(jì)算加速的效果，將已發(fā)現(xiàn)的量子算法分為三類48：“相對(duì)黑盒”指數(shù)加速的量子算法、指數(shù)加速的量子算法和非指數(shù)加速的量子算法?！跋鄬?duì)黑盒”指數(shù)加速的量子算法在計(jì)

26、算機(jī)科學(xué)中，量子黑盒是執(zhí)行某種計(jì)算任務(wù)的幺正操作。它可以作為量子計(jì)算的一段子程序，當(dāng)量子黑盒的輸入為量子迭加態(tài)時(shí)，與輸入為經(jīng)典態(tài)時(shí)相比，它可以實(shí)現(xiàn)計(jì)算的指數(shù)加速，對(duì)應(yīng)的算法稱為“相對(duì)黑盒”指數(shù)加速的量子算法?！跋鄬?duì)黑盒”指數(shù)加速的量子算法的一個(gè)典型代表是杜奇-約薩（Deutsch-Jozsa ）問題及其算法49。如果允許杜奇約薩問題有邊界誤差（bound error）的解，經(jīng)典計(jì)算機(jī)也可以有多項(xiàng)式的解，此時(shí)量子算法并沒有什么優(yōu)勢。而在要求精確解的時(shí)候，杜奇-約薩問題的經(jīng)典解沒有多項(xiàng)式算法，量子算法具有指數(shù)加速的優(yōu)勢。杜奇-約薩問題是指：假設(shè)有一個(gè)n 位輸入的量子黑盒，它的計(jì)算函數(shù)為 如果對(duì)所有

27、的輸入 都是0或者1，稱 是常數(shù)函數(shù)；如果對(duì)一半的輸 入 ， ，對(duì)另一半的輸入 則 稱 是對(duì)稱函數(shù)。杜奇約薩問題希望判定 是否為常數(shù)函數(shù)。如果利用經(jīng)典態(tài)作為輸入，共需 次計(jì)算來解決此問題。而利用量子迭加態(tài)作為輸入，則只需要運(yùn)行一次量子黑盒，就可以得到肯定的結(jié)果，過程如下：首先，利用1個(gè)輔助量子位，將 量子位的沃爾什哈德曼變換 作用在 ，得到輸入態(tài) 然后進(jìn)行 操作，得到再對(duì)前個(gè)輸入量子位進(jìn)行沃什-哈德曼操作，得到此時(shí)測量前 個(gè)量子位，如果測得時(shí)，說明 是常數(shù)函數(shù)；如果測得的狀態(tài)不是 態(tài)時(shí)，說明 是對(duì)稱函數(shù)?？梢?，相對(duì)于經(jīng)典算法的次計(jì)算，杜奇-約薩量子算法只需一次黑盒計(jì)算就解決問題，實(shí)現(xiàn)了“相對(duì)黑

28、盒”的指數(shù)加速。肖爾大數(shù)質(zhì)因子分解算法肖爾大數(shù)質(zhì)因子分解算法3是一個(gè)典型的實(shí)現(xiàn)指數(shù)加速的量子算法。根據(jù)經(jīng)典計(jì)算復(fù)雜性理論，分解大數(shù)質(zhì)因子屬于NP 2困難問題（但不是NPC 問題），而在量子計(jì)算機(jī)上利用肖爾大數(shù)質(zhì)因子分解算法，可以在多項(xiàng)式時(shí)間解決這一問題，實(shí)現(xiàn)了計(jì)算的指數(shù)加速。找兩個(gè)質(zhì)數(shù)的乘積是一個(gè)很容易進(jìn)行的運(yùn)算?？墒侨绻催^來，把一個(gè)乘積分解成兩個(gè)質(zhì)數(shù)的乘積，則相對(duì)于前者是一個(gè)麻煩得多的問題。一般地，一個(gè)大數(shù)N ，我們要將之分解，約需要計(jì)算步。(14(15（16）（17） 2 可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問題稱為NP問題。無法做到在多項(xiàng)式時(shí)間驗(yàn)證解的正確性的問題是NP困難問題。3

29、RSA是一個(gè)Internet加密與鑒權(quán)系統(tǒng)，它使用Ron Rivest、Adi Shamir及Leonard Adleman在1977年開發(fā)的一個(gè)算法。Communications of CCF 2008/7 21計(jì)算的步數(shù)與大數(shù)的位數(shù)成指數(shù)增長關(guān)系。1個(gè)600位的大數(shù)，使用目前最快的計(jì)算機(jī)，居然要用比整個(gè)宇宙的年齡還要長的時(shí)間才能分解出。目前廣泛使用的RSA 3密鑰系統(tǒng)就是基于假定不存在快的大數(shù)分解算法，從而使得RSA 密鑰系統(tǒng)受到巨大挑戰(zhàn)，同時(shí)也推動(dòng)了人類對(duì)量子計(jì)算機(jī)的研究。在量子計(jì)算機(jī)上實(shí)現(xiàn)肖爾的大數(shù)分解算法，分解一個(gè)L位的大數(shù)，計(jì)算步數(shù)下降為 。假定要分解的大數(shù)為N ，肖爾算法的過程如

30、下：（1）隨機(jī)選取 （ 并與N 互質(zhì)），用量子算法求函數(shù) 的周期T 。（2）若T 為奇數(shù)，則返回1，重新選??；若T 為偶數(shù)，則取。（3）求得y 后，用歐幾里德輾轉(zhuǎn)相除法求得 和 分別與N 的最大公約數(shù)，則可以找到質(zhì)因子。以上算法的關(guān)鍵在于求得函數(shù)的周期T ，這是量子計(jì)算機(jī)體現(xiàn)其優(yōu)越性的地方。這一算法在經(jīng)典計(jì)算機(jī)上執(zhí)行時(shí)，需要的物理資源和計(jì)算步驟是隨著位數(shù)指數(shù)增加的，而在量子計(jì)算機(jī)執(zhí)行肖子算法創(chuàng)是多項(xiàng)式增加的。格洛弗量子搜索算法1996年，格洛弗提出了非結(jié)構(gòu)化數(shù)據(jù)庫的量子搜索算法，又稱為格洛弗算法45。該算法的時(shí)間復(fù)雜度為 ，與經(jīng)典算法的平均復(fù)雜度為O(N相比，格洛弗量子搜索算法實(shí)現(xiàn)了計(jì)算的平方

31、加速。格洛弗量子搜索算法要解決的問題是：在 個(gè)量子比特的非結(jié)構(gòu)化數(shù)據(jù)庫中， 有個(gè)量子基態(tài) ，其中只有一個(gè)目標(biāo)態(tài) 滿足某一量子黑盒的查詢函數(shù) ，其它量子態(tài)都使得查詢函數(shù) 。量子搜索算法是以盡可能大的概率將目標(biāo)態(tài) 找到。格洛弗搜索算法包括以下步驟：（1）數(shù)據(jù)庫初始化。首先， 量子比特的寄存器處在 態(tài)上，實(shí)施 量子比特的沃爾什哈德曼操作 ，此時(shí)數(shù)據(jù)庫被初始化為一個(gè)平均迭加態(tài)（2）進(jìn)行格洛弗搜索迭代 次，然后對(duì) 量子比特狀態(tài)進(jìn)行測量，以一定概率得到目標(biāo)量子態(tài) 。格洛弗搜索迭代包括四個(gè)子步驟：步驟1：反轉(zhuǎn)目標(biāo)態(tài) 的相位，而其它態(tài)保持不變。步驟2：進(jìn)行 量子比特的沃爾什哈德曼變換， 。步驟3：反轉(zhuǎn)除 態(tài)之

32、外的所有基態(tài)的相位，而保持 態(tài)不變。步驟4：進(jìn)行 量子比特的沃爾什哈德曼變換， 。步驟2步驟4的過程，相當(dāng)于對(duì)平均量子態(tài)進(jìn)行了一個(gè)反轉(zhuǎn)，將這個(gè)操作稱為擴(kuò)散操作，記為D ?？梢詮囊环N更直觀的幾何可視化角度去理解格洛弗量子搜索算法，即在以 態(tài)和 態(tài)為基矢的二維希爾伯特空間中，格洛弗迭代操作G 可以表示為單個(gè)格洛弗搜索迭代G 的整體作用可以看作是在二維平面內(nèi)沿逆時(shí)針方向旋轉(zhuǎn)2 角度。因此，在連續(xù)j 次搜索迭代之后，數(shù)據(jù)庫的量子態(tài)變?yōu)?如果要以盡可能大的概率搜索到目標(biāo)態(tài)，則需要盡可能滿足條件 ，因此最佳的搜索迭代步 其中 INT 表示對(duì)實(shí)數(shù)取整。對(duì)于某個(gè)特定的數(shù)據(jù)庫， 不一定恰好等于，因此格（19 ）

33、（20 ）（21 ）（18 ）專題報(bào)道Cover FeaturesCommunications of CCF 2008/722洛弗搜索算法的最大成功率不一定為100%，它是一個(gè)隨迭代步數(shù)j 變換的周期性函數(shù)。相位匹配與精確量子搜索算法雖然格洛弗算法的搜索成功率很大，但是其有缺陷。它的搜索成功率只是在只有4個(gè)數(shù)據(jù)的時(shí)候才是100%。即使在數(shù)據(jù)庫很大的時(shí)候，如果標(biāo)記態(tài)的數(shù)量比較大，格洛弗算法的成功率也會(huì)很低。例如，如果標(biāo)記態(tài)的數(shù)目是數(shù)據(jù)庫的一半的時(shí)候，標(biāo)準(zhǔn)的格洛弗算法就失敗了。有一個(gè)流行的錯(cuò)誤，格洛弗等人認(rèn)為，如果將格洛弗算法中的2個(gè)相位取反換成任意角度的轉(zhuǎn)動(dòng)，搜索算法依然可以成功。后來證明，格洛

34、弗的這個(gè)判斷是錯(cuò)誤的。在一般的相位轉(zhuǎn)動(dòng)下，2個(gè)轉(zhuǎn)動(dòng)的角度，也就是2個(gè)相位必須滿足相位匹配條件51-53。相位匹配條件是量子搜索算法成功的必要條件。而格洛弗算法的成功率不是100%的主要原因是用1個(gè)固定的180度轉(zhuǎn)動(dòng)對(duì)任意的數(shù)據(jù)庫進(jìn)行搜索，這種粗糙的相位轉(zhuǎn)動(dòng)選擇導(dǎo)致了搜索成功率的降低。2001年構(gòu)建的改進(jìn)格洛弗算法，可以精確地給出標(biāo)記態(tài)47。對(duì)于含有1個(gè)目標(biāo)態(tài)的N 條目非結(jié)構(gòu)化量子數(shù)據(jù)庫，該算法經(jīng)過數(shù)次搜索迭代，可以以100%的成功率將目標(biāo)態(tài)搜索到。其算法過程如下。對(duì)于N 個(gè)基態(tài)的平均迭加態(tài)的數(shù)據(jù)庫，其相位輕動(dòng)角是：特別指出，這里的角度不是唯一的。這里有個(gè)最小的搜索次數(shù)J op ，比這個(gè)數(shù)大的任

35、意整數(shù)也都可以。最近與格洛弗算法有關(guān)的一個(gè)發(fā)展是定點(diǎn)量子搜索算法54,55。定點(diǎn)量子搜索算法中隨著搜索步驟的增加，體系的狀態(tài)越來越接近目標(biāo)態(tài)，不會(huì)像格洛弗算法那樣是搜索步驟的周期函數(shù)。但是這個(gè)算法所需要的步驟是O(3n ，比經(jīng)典搜索算法需要的步驟還多。但是這個(gè)算法在空間資源上比經(jīng)典算法節(jié)約。結(jié)語本文介紹了量子信息的理論基礎(chǔ)、常見的量子通信和主要的量子算法。量子信息是一個(gè)迅速發(fā)展的領(lǐng)域，還有許多重要的研究內(nèi)容，如量子計(jì)算機(jī)的模型理論56，量子態(tài)識(shí)別和量子操作的識(shí)別57,58、消相干控制59、量子糾錯(cuò)60和量子編程語言61等。此外，將量子力學(xué)中的波粒二像性引入到量子計(jì)算中，有可能提高量子計(jì)算的能力

36、，建立經(jīng)典算法和量子算法之間的聯(lián)系62。量子信息學(xué)是量子力學(xué)和信息科學(xué)結(jié)合產(chǎn)生的交叉學(xué)科。今后，隨著更多方面研究的結(jié)合，還會(huì)有新的研究內(nèi)容出現(xiàn)。龍桂魯 清華大學(xué)物理系、清華信息科學(xué)與技術(shù)國家實(shí)驗(yàn)室（籌）教授，博士生導(dǎo)師?，F(xiàn)就職于清華大學(xué)原子分子與納米科學(xué)重點(diǎn)實(shí)驗(yàn)室。1987年在清華大學(xué)獲得博士學(xué)位。主要研究興趣：量子計(jì)算、量子通信和核磁共振量子計(jì)算等。1 P. Benioff, The computer as a physical system: a micro-scopic quantum mechanical Hamiltonian model of com-puters as repre

37、sented by Turing machines. J. Stat. Phys.,1980, 22(5:563-5912 R. P. Feymnman. Simulating physics with computers.Int. Journal of Theor. Phys., 1982, 21(6:467-4883 P. Shor. Algorithms for quantum computaion: discretelogarithm factoring. Proc. 35th Annual Symposium oncomputer Science, IEEE, 1992:181-18

38、24 C. H. Bennett and G. Brassard. Quantum cryptogra-phy: public key distribution and coin tossing. Proc. IEEE 參考文獻(xiàn)（22）Communications of CCF 2008/723 Int. Conf. on Computers, Systems and Signal Processing,Bangalore, India (IEEE, New York, 1984:175-1795 C. H. Bennett, G. Brassard, C. Crepeau, et al. T

39、ele-porting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys. Rev. Lett.,1993, 70(13:18956 李承祖, 黃明球, 陳平行等. 量子通信和量子計(jì)算. 長沙: 國防科技大學(xué)出版社, 20017 張永德. 量子信息物理原理. 北京: 科學(xué)出版社,20068 曾謹(jǐn)言, 裴壽鏞主編. 量子力學(xué)新進(jìn)展. 第一輯，北京: 北京大學(xué)出版社，20009 曾謹(jǐn)言, 裴壽鏞, 龍桂魯主編. 量子力學(xué)新進(jìn)展. 第二輯, 北京:北京大學(xué)出版社, 200110

40、 曾謹(jǐn)言, 龍桂魯, 裴壽鏞主編. 量子力學(xué)新進(jìn)展. 第三輯, 北京:清華大學(xué)出版社, 200311 龍桂魯, 曾謹(jǐn)言, 裴壽鏞主編. 量子力學(xué)新進(jìn)展. 第四輯, 北京:清華大學(xué)出版社, 200612 喀興林. 高等量子力學(xué). 北京:高等教育出版社, 200113 曾謹(jǐn)言. 量子力學(xué), 卷I, 卷II. 第三版, 北京:科學(xué)出版社, 200014 R. Shankar. Principles of Quantum Mechanics. 2nd edi-tion,Plenum Press, New York, 198015 Gui Lu Long, Yi-Fan Zhou, Jia-Qi Jin

41、, Yang Sun,Hai-Woong Lee. Density Matrix in QuantumMechanicsand Distinctness of Ensembles Having the Same Com-pressed Density Matrix, Foundations of Physics, 2006,36(4:1217-124316 W. K. Wooters, W. H. Zurek. A single quantum cannotbe cloned. Nature, 1982, 299:802-80317 T. Gao, F L yan, Z X Wang, Y Q

42、 Li. Quantum proba-bilistical cloning and computation, Front. Comput. Sci.China, 2008, 2(2:179-18918 D. Bohm. Quantum theory. Prentice Hall, EnglewoodCliffs, 199519 D. M. Greenberger, M. A. Horne, Z. Zerlinger. Going be-yond Bell's theorem. in Bell's theorem, quantum theory,and conceptions o

43、f the universe, Dordrecht: Kluwer, M.Kafatos (Ed., 198920 J. Bell. On the Einstein-Podolsky-Rosen paradox.Physics, 1964, 1:195-20021 J. F. Clauser, M. A. Horne, A. Shimony, et al. Proposed experimental to test local-hidden-variable theories. Phys.Rev. Lett., 1969, 23:880-88422 A. Aspect, Dalibard, G

44、. Roger. Experimental test of Bell's inequalities using for continuous variable systems.Phys. Rev. Lett., 1982, 49:1804-180723 X. H. Gao, A. Sergio, K. Chen, S. M. Fei and X. Q.Li-Jost. Entanglement of formation and concurrence for mixed states, Front. Comput. Sci. China, 2008, 2(2:114-12924 Y.

45、C. Wu and G. C. Guo. High-dimension Bell inequalities. Front. Comput. Sci. China, 2008, 2(2:190-19225 Z. Zhao et al. Experimental demonstration of vephotonentanglement and open-destination teleportation. Nature, 2004, 430:54-5826 J. T. Barreiro et al. Generation of hyperentangled photonpairs. Phys.

46、Rev. Lett., 2005, 95:26050127 X. H. Li and F. G. Deng. Controlled teleportation. Front.Comput. Sci. China, 2008, 2(2:147-16028 M. Zukowski, A. Zeilinger, A. Horne, et al. Event-ready-detectors Bell experiment via entanglement swapping.Phys. Rev. Lett., 1993, 70(26:4287-429029 C. H. Bennett and S. J.

47、 Wiesner. Communication viaone-and two-particle operators on Einstein-Podolsky- Rosen states. Phys. Rev. Lett., 1992, 69:2881-288430 X. S. Liu, G. L. Long, D. M. Tong and Feng Li. General scheme for superdense coding between multi- parties. Phys. Rev. A, 2002, 65:02230431 A. Crudka, A. Wojcik A. Sym

48、metric scheme for super-dense coding between multipaties. Phys Rev A, 2002, 66(1: 01430132 D. X. Wei, X. D. Yang, J. Luo, X. P. Sun, X. Z. Zeng and M. L. Liu. NMR experimental implementation of three-parties quantum superdense coding. Chinese Science Bul-letin, 2004, 49(5:423-42633 X. Li et al. Quan

49、tum dense coding exploiting a bright Einstein-Podolsky-Rosen beam. Phys. Rev. Lett., 2008, 88:04790434 X. Fang et al. Experimental implementation of dense coding using NMR. Phys. Rev. A, 2000, 61:02230735 J. Barreiro et al. Beating the channel capacity limit for linear photonic superdense coding. Na

50、ture Physics, 2008,4:282-28636 C. H. Bennett. Quantum cryptography using any two nonorthogonal states. Phys. Rev. Lett., 1992, 68:3121- 312437 W. Y. Hwang, I. G. Koh, Y. D. Han. Quantum cryptography without public announcement of bases. Phys. Lett.A, 1998, 244:489-49438 A. K. Ekert. Quantum cryptogr

51、aphy based on Bell's theorem. Phys. Rev. Lett., 1991, 67:661-66339 C. H. Bennett, G. Brassard, N. D. Mermin. Quantum cryptography without Bell's theorem. Phys. Rev.專題報(bào)道Cover Features 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 Lett.,1992, 68:557-669 G. L. Long, X. S.

52、 Liu. Theoretically e±cient high-capacity quantum-key-distribution schemes. Phys. Rev.A, 2002, 65:032302 A. Cabello. Quantum key distribution in the Holevo limit. Phys. Rev. Lett., 2000, 85:5635-5638 P. Xue, C. F. Li, G. C. Guo. Quantum key distributionvia quantum encryption. Phys. Rev. A, 2002

53、, 65:022317 K. BostrÄom and T. Felbinger. Deterministic Secure Direct Communication Using Entanglement. Phys. Rev. Lett., 2002, 89:187902 F. G. Deng, G. L. Long and X. S. Liu. Two-step quantum direct communication protocol using the Einstein- Podolsky- Rosen pair block. Phys. Rev. A, 2003,68(4:

54、042317; Secure direct communication with a quantum one-time pad. Phys. Rev. A, 2004, 69(5:052319;Quantum secure direct communication network with Einstein-Podolsky-Rosen pairs. Phys. Lett. A, 2006,359(5:359-365 L. Grover. A fast quantum mechanical algorithm fordatabase search. Proc. 28th Annual ACM

55、Symposium on Theory of Computing, ACM, New York, 1996, pp.212-219 M. Boyer, G. Brassard, P. Hoyer, A. Tapp. Strengthand weakness of quantum computation. Fortschr. Phys., 1998, 46:493-505 G. L. Long, Grover algorithm with zero failure rate, Phys.Rev. A, 2001, 64:022307 J. Preskill. Quantum information and quantum computation. California Institute of Technology, 1998 D. Deutsch, R. Jozsa. Rapid solution of problems by quant