王幫海，龔洪波

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州　510006）

量子計(jì)算與量子信息簡(jiǎn)介

王幫海，龔洪波

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006）

0　引言

電子計(jì)算機(jī)的產(chǎn)生與發(fā)展不僅深刻地改變了人們的生活，也深刻的影響著人們的思想。特別是計(jì)算機(jī)網(wǎng)絡(luò)的應(yīng)用與發(fā)展，計(jì)算機(jī)與人類生活的密切程度，已經(jīng)遠(yuǎn)遠(yuǎn)超出了人們當(dāng)初的想象。計(jì)算機(jī)的計(jì)算速度、存儲(chǔ)容量都遵循著Moore定律：每三年翻一番［1］。按照這個(gè)速度，十多年以后計(jì)算機(jī)存儲(chǔ)單元將是單個(gè)原子，屆時(shí)就會(huì)出現(xiàn)集成電路中電流不穩(wěn)定、熱量在技術(shù)上難以散發(fā)以及受到量子效應(yīng)干擾等現(xiàn)象［2］。同時(shí)，傳統(tǒng)的計(jì)算機(jī)體系結(jié)構(gòu)――馮諾依曼結(jié)構(gòu)在人類探索世界奧妙的雄心壯志面前顯得力不從心［3］。人們從馮諾依曼結(jié)構(gòu)出發(fā)，不斷地提出各種新型結(jié)構(gòu)的計(jì)算機(jī)。

量子計(jì)算就是新型結(jié)構(gòu)的計(jì)算模型之一 （值得一提的還有生物計(jì)算或分子計(jì)算）。量子計(jì)算與量子信息（這兩方面一般合起來(lái)稱作 “量子信息學(xué)”）是量子力學(xué)、計(jì)算機(jī)科學(xué)與信息理論等交叉融合產(chǎn)生的新興學(xué)科［4］。本文介紹量子計(jì)算的起源、基本概念、以及與經(jīng)典相比量子基本特性、基本原理和它們的應(yīng)用。本文力求避免數(shù)學(xué)符號(hào)、物理概念，希望具有一點(diǎn)線性代數(shù)知識(shí)的讀者能對(duì)量子信息學(xué)有一個(gè)初步的了解。

1　量子信息學(xué)發(fā)展簡(jiǎn)史

眾所周知，20世紀(jì)初就發(fā)現(xiàn)了量子力學(xué)，但是直到20世紀(jì)30年代才差不多被人們所普遍知曉。當(dāng)物理學(xué)家在嘗試著用計(jì)算機(jī)模擬量子力學(xué)時(shí)，產(chǎn)生了量子力學(xué)可能會(huì)使（量子）計(jì)算比經(jīng)典計(jì)算更先進(jìn)的念頭。因?yàn)閷?duì)n個(gè)量子比特來(lái)說(shuō)，總共需要2n個(gè)復(fù)數(shù)才能完全描述它，而不是2n個(gè)。量子力學(xué)的這種指數(shù)級(jí)的狀態(tài)空間，使人們自然的想，它有沒(méi)有包含一個(gè)超乎我們想象的更大、更強(qiáng)的計(jì)算資源。1982年，理查德費(fèi)曼覺(jué)得也許基于量子力學(xué)的計(jì)算機(jī)可以執(zhí)行任務(wù)更高效，因?yàn)閭鹘y(tǒng)計(jì)算機(jī)似乎需要指數(shù)開(kāi)銷模擬量子力學(xué)，因而產(chǎn)生了量子計(jì)算可能比傳統(tǒng)計(jì)算更有優(yōu)勢(shì)的想法。1985年，英國(guó)牛津大學(xué)教授D.Deutsch引進(jìn)量子計(jì)算線路模型和量子通用邏輯門組，提出量子圖靈機(jī)的概念，使量子計(jì)算開(kāi)始具備數(shù)學(xué)的基本型式。

更早的，有關(guān)量子信息學(xué)的研究可以追溯到幾十年前的可逆計(jì)算的研究和貝爾不等式的發(fā)現(xiàn)，但真正引起人們普遍關(guān)注并掀起研究熱潮的是二十世紀(jì)九十年代中期。在這期間，Shor提出了量子并行計(jì)算的大數(shù)因數(shù)分解算法，Grover提出了快速的基于無(wú)先驗(yàn)結(jié)構(gòu)信息的量子搜索算法。大數(shù)因數(shù)的快速分解宣示著目前廣泛應(yīng)用于密碼通訊中的公鑰體制RSA算法不再具有計(jì)算安全性；Grover快速量子搜索算法能夠快速地找到DES加密算法算法密鑰，意味著DES算法將不堪一擊［5］。

2　量子比特與量子門

一般來(lái)說(shuō)，經(jīng)典電子計(jì)算機(jī)處理的只有“0”、“1”兩個(gè)基本狀態(tài)，往往用電壓或者電流有無(wú)來(lái)表示，或者不同的數(shù)值，例如+5伏電壓表示1，-3伏電壓表示0。

量子計(jì)算處理的基本元素是量子比特。量子力學(xué)系統(tǒng)由希爾伯特（Hilbert）空間中的向量表示，表示量子態(tài)的向量稱狀態(tài)向量。一般情況下，具有d個(gè)可完美區(qū)分的量子態(tài)的量子系統(tǒng)能夠用復(fù)線性空間Cd中的一個(gè)單位向量描述。這個(gè)最簡(jiǎn)單的情況是d=2。這樣的系統(tǒng)，我們稱作一個(gè)量子比特。因?yàn)椋且粋€(gè)二維復(fù)向量空間的正交基，所以任意向量］可以表示為，其中a和b都是復(fù)數(shù)。］被稱為一個(gè)量子比特，常被稱作疊加態(tài)（superposition），］稱為計(jì)算基態(tài)，也不嚴(yán)格的稱為量子中的“0”、“1”。與經(jīng)典比特不同，我們不能通過(guò)測(cè)量量子狀態(tài)來(lái)確定它是哪個(gè)具體的量子狀態(tài)，也就是得到a和b的值。事實(shí)上，量子力學(xué)告訴我們，只能得到量子狀態(tài)的有限信息。也就是說(shuō)，一個(gè)量子態(tài)往往不是確定的，只是這兩種基態(tài)的線性組合，也就是說(shuō)，一個(gè)量子態(tài)中含有兩個(gè)變量參數(shù)，這樣n個(gè)量子比特里至少含有2的n次方信息。在測(cè)量量子比特時(shí)，我們得到態(tài)的概率為|a|2，態(tài)的概率為|b|2。由于概率和總是等于1，當(dāng)然就有|a|2+|b|2= 1。這就是量子態(tài)的歸一化，從幾何意義上看，就是要求量子比特的狀態(tài)歸一化到長(zhǎng)度1。所以，一般而言，量子比特的狀態(tài)是二維復(fù)向量空間中的單位向量。例如，一個(gè)比特量子態(tài)。如果使用基｝進(jìn)行測(cè)量，50%的可能得到，50%的可能得到］，如果使用基｝進(jìn)行測(cè)量，則得到概率）是100%，得到的概率是0。這種奇妙的結(jié)果是量子力學(xué)所獨(dú)有的，進(jìn)一步的了解可參照參考文獻(xiàn)［1-5］等。

至于為什么量子比特用向量或者矩陣表示 （等同的，也可用波函數(shù)表示，這里不詳述），這緣于量子力學(xué)的基本假設(shè)。自從牛頓創(chuàng)導(dǎo)模型與數(shù)學(xué)相結(jié)合的科學(xué)研究方法以后，幾乎物理學(xué)的每一步發(fā)展也離不開(kāi)模型和數(shù)學(xué)。把實(shí)際的物理問(wèn)題簡(jiǎn)化并使之能直接應(yīng)用數(shù)學(xué)就是物理模型，采用的辦法往往就是作“假設(shè)”。對(duì)于量子領(lǐng)域的問(wèn)題，人們很少有直接的感覺(jué)經(jīng)驗(yàn)，“假設(shè)”就顯得尤其重要。量子力學(xué)的假設(shè)是先驅(qū)們經(jīng)過(guò)了大量猜測(cè)和摸索，甚至是長(zhǎng)期的嘗試與失敗而得到的。它把物理世界和數(shù)學(xué)描述聯(lián)系了起來(lái)，它界定了物理理論或者物理概念的適用范圍。任何一個(gè)物理理論都有其適用范圍。對(duì)于我們目的而言，堅(jiān)持這些假設(shè)就足夠了［6］。

3　量子基本特性及其應(yīng)用

量子力學(xué)為信息學(xué)帶來(lái)了這些令人耳目一新的現(xiàn)象的根源在于量子的兩個(gè)基本特性：量子線性疊加和量子糾纏。

（1）量子線性疊加

量子線性疊加原理是指任一量子系統(tǒng)都可以表示為描述量子系統(tǒng)不同狀態(tài)（量子態(tài)）的線性組合，表現(xiàn)為如果輸入是多個(gè)可能輸入狀態(tài)的線性組合時(shí)，輸出態(tài)也將是所有輸入態(tài)對(duì)應(yīng)輸出態(tài)的線性組合，這是量子物理最基本、最顯著的原理，也是量子并行計(jì)算的核心［3，5］。

為了原理性的描述量子并行計(jì)算的機(jī)制，人們常常以Deutsch問(wèn)題為例說(shuō)明。設(shè)一個(gè)函數(shù)f，若f（0）=f （1），則稱f為常數(shù)函數(shù)，否則稱為平衡函數(shù)?，F(xiàn)假設(shè)一個(gè)量子裝置可以計(jì)算f（x），現(xiàn)在的任務(wù)是判斷f（x）是常數(shù)函數(shù)還是平衡函數(shù)。很明顯，如果是經(jīng)典輸入，必須運(yùn)行這個(gè)裝置兩次才能得到結(jié)果，而如果是量子輸入則只需運(yùn)行量子裝置一次。具體運(yùn)算機(jī)制，讀者可參考文獻(xiàn)［4］等。

（2）量子糾纏及其應(yīng)用

此時(shí)此地發(fā)生的某件事情能夠在萬(wàn)里之外的同一時(shí)刻引起某種反應(yīng)，這可能嗎？我們對(duì)某一個(gè)觀測(cè)量的測(cè)量，在同一時(shí)刻，千里之外，或者世界的另一頭，甚至宇宙的邊緣（假如存在），一個(gè)類似的行為也會(huì)發(fā)生，這可能嗎？令人驚奇的是，與我們的直覺(jué)相反，這種現(xiàn)象確實(shí)存在，這就是“量子糾纏”（quantum entanglement）。糾纏中的兩個(gè)粒子互相關(guān)聯(lián)在一起，無(wú)論它們之間的距離多么遙遠(yuǎn)［7］。自從1935年薛定諤創(chuàng)造“糾纏”［8］這個(gè)詞來(lái)描述這種關(guān)聯(lián)以來(lái)，人們對(duì)“糾纏”的理解與探索就沒(méi)有停止過(guò)。量子糾纏是量子力學(xué)獨(dú)特的重要的資源，處于量子信息學(xué)的中心位置，在量子計(jì)算與量子信息的應(yīng)用上起關(guān)鍵作用，參考文獻(xiàn)［9］把它比作經(jīng)典世界中青銅器時(shí)代中的鐵的地位。

很明顯，量子糾纏涉及到兩個(gè)或者兩個(gè)以上粒子的復(fù)合系統(tǒng)。數(shù)學(xué)上用張量積“?”描述系統(tǒng)間的關(guān)聯(lián)。例如，密度矩陣表示系統(tǒng)以pi的概率處于狀態(tài)ρi?σi，而ρi描述的是第一個(gè)系統(tǒng)的狀態(tài)，σi描述的是第二個(gè)系統(tǒng)的狀態(tài)。張量積的運(yùn)算規(guī)則，感興趣的讀者可參考文獻(xiàn)［9］等。

（1）量子超密編碼

超密編碼（superdense coding）是利用兩個(gè)量子態(tài)糾纏特性的量子力學(xué)的一個(gè)簡(jiǎn)單的應(yīng)用，最初由Bennett和Wiesner提出［9，10］。具體來(lái)說(shuō)，就是收送雙方共同擁有量子糾纏態(tài)，通過(guò)量子信道傳送量子態(tài)，實(shí)現(xiàn)發(fā)送者發(fā)送一個(gè)量子比特，接收者得到兩個(gè)經(jīng)典比特的信息過(guò)程。習(xí)慣性的，把涉及的兩方分別稱為Alice和Bob。應(yīng)用的情形是他們彼此相距很遠(yuǎn)，Alice要給Bob傳送兩個(gè)經(jīng)典比特信息，但是只允許發(fā)送一個(gè)單量子比特給Bob。這種超出經(jīng)典的直覺(jué)想象的任務(wù)，利用量子超密編碼就可以完成。

（2）量子隱形傳態(tài)

4　量子基本原理及其應(yīng)用

量子世界有著與經(jīng)典世界不同的特性，這些特性往往使“經(jīng)典的”我們很難理解。下面不作證明的，介紹這些量子基本原理。事實(shí)上，數(shù)學(xué)上證明并不難，感興趣的讀者，可參考［1-5］、［9］、［13］等。

定理1：不能同時(shí)精確知道一個(gè)粒子的位置與動(dòng)量。這就是大家所熟知的海森堡測(cè)不準(zhǔn)原理?，F(xiàn)在我們一般把它稱為海森堡測(cè)不確定性原理。

定理2：無(wú)法可靠區(qū)分兩個(gè)非正交量子態(tài)。

定理3：未知的量子態(tài)不能完全被克隆。這與經(jīng)典非常不同，經(jīng)典計(jì)算機(jī)之所以有今天這么廣泛的應(yīng)用或許與能“隨意”拷貝密不可分。

上面這三個(gè)基本原理在本質(zhì)上是統(tǒng)一的［13］。這些也是量子保密通信具有無(wú)條件安全的基礎(chǔ)。

獨(dú)立于量子計(jì)算，現(xiàn)在公認(rèn)的最早的量子密碼術(shù)出現(xiàn)于上個(gè)世紀(jì)70年代。當(dāng)時(shí)還是研究生的Stephen Wiesner提出了量子貨幣的概念，希望用量子力學(xué)的方法增強(qiáng)鈔票的防偽能力。當(dāng)時(shí)的想法遠(yuǎn)遠(yuǎn)超前，他的論文處處碰壁，直到1983年才最終正式發(fā)表。但正是它啟發(fā)了隨后的BB84量子密鑰分配協(xié)議的提出，從而引發(fā)了一場(chǎng)密碼學(xué)技術(shù)革命［6］。

量子密碼術(shù)一般包括兩種不同的形式：量子密鑰分配（QKD）以及從加密算法本身出發(fā)實(shí)現(xiàn)量子加密。量子密鑰分配是指通信雙方無(wú)須事先共享秘密的情況下產(chǎn)生一個(gè)隨機(jī)安全密鑰的過(guò)程。這樣通信雙方無(wú)須事先交換密鑰就能進(jìn)行秘密通信，因此量子密鑰分配是量子密碼的基礎(chǔ)。海森堡不確定原理則是量子密鑰分配的理論保證。因?yàn)楹Ｉげ淮_定性原理告訴我們對(duì)一個(gè)量子態(tài)的測(cè)量必將引起原來(lái)量子態(tài)的擾動(dòng)，對(duì)量子系統(tǒng)的任何測(cè)量都無(wú)法獲取測(cè)量前的量子信息。這就意味著，一旦竊聽(tīng)者竊聽(tīng)量子信道的量子態(tài)時(shí)，必將對(duì)量子態(tài)造成干擾，對(duì)Alice和Bob雙方的測(cè)量結(jié)果發(fā)生變化，從而提醒非法用戶的存在。

5　發(fā)展與展望

量子信息學(xué)在不斷的發(fā)展，其研究?jī)?nèi)容也在不斷的擴(kuò)充。目前，這一研究領(lǐng)域主要包含三個(gè)方向：（1）量子計(jì)算機(jī)和量子算法；（2）量子密碼學(xué)；（3）相關(guān)的信息理論問(wèn)題。方向（3）主要是將傳統(tǒng)的信息熵、信道容量等信息學(xué)理論問(wèn)題在量子力學(xué)層面推廣到新內(nèi)容以及帶有量子力學(xué)獨(dú)特特性的量子糾纏度的度量，等等。它是量子信息學(xué)發(fā)展比較遲的一個(gè)分支，有些問(wèn)題甚至距離形成統(tǒng)一的定論都比較遙遠(yuǎn)，至今尚未完全成熟［4］。

目前，量子計(jì)算的實(shí)現(xiàn)采用的技術(shù)有核磁共振、光量子、量子幾何相位、超導(dǎo)/介觀電路等［4］。無(wú)論哪種方案，目前最大的問(wèn)題是量子退相干。量子退相干是指量子系統(tǒng)不可避免地會(huì)與環(huán)境自發(fā)的耦合，導(dǎo)致其狀態(tài)受到干擾而出現(xiàn)不可逆的錯(cuò)誤，量子效應(yīng)消失。目前量子系統(tǒng)能保持相干的時(shí)間非常短，還不足以保持到量子計(jì)算達(dá)到實(shí)用的程度。

令人鼓舞的是，量子保密通信，已經(jīng)進(jìn)入實(shí)用階段，并且中國(guó)走在了世界的前列。2014年4月，中國(guó)開(kāi)始鋪設(shè)目前世界上最長(zhǎng)的包括連接北京與上海的2000多公里的量子通信網(wǎng)絡(luò)［14］。

由于大型量子計(jì)算機(jī)還未建立，因此量子信息對(duì)計(jì)算機(jī)科學(xué)的大部分貢獻(xiàn)還處于理論階段。但是一旦大型量子計(jì)算機(jī)建立成功，我們期望這些理論能應(yīng)用在理論家難以解釋的方面，就像我們今天在經(jīng)典啟發(fā)下成功發(fā)現(xiàn)了簡(jiǎn)單量子算法。歷史告訴我們，很多這樣的新工具最初是違反常識(shí)的，但是當(dāng)我們掌握了它們之后，這些工具將會(huì)帶領(lǐng)我們以全新的方式來(lái)認(rèn)識(shí)世界［15］。

［1］佐川弘幸，吉田宣章著.突破經(jīng)典信息科學(xué)的極限――量子信息論.宋鶴山，宋天譯.大連理工大學(xué)出版社，2007，9.

［2］王幫海.基于糾纏破壞信道與糾纏目擊者的可分標(biāo)準(zhǔn)研究.博士論文：中山大學(xué)計(jì)算機(jī)系，2011，6.

［3］戴葵，宋輝，劉蕓，譚明峰.量子信息技術(shù)引論.湖南：國(guó)防科技大學(xué)出版社，2001，3.

［4］何廣平著.通俗量子信息學(xué).北京：科學(xué)出版社，2012.

［5］趙生妹，鄭寶玉.量子信息處理技術(shù).北京：北京郵電大學(xué)出版社，2010-1.

［6］金尚年.量子力學(xué)的物理基礎(chǔ)和哲學(xué)背景.上海：復(fù)旦大學(xué)出版社，2007-7.

［7］A.D.Aczel.Entanglement：The greatest mystery in physics.John Wileyand Sons Ltd.2002.莊星來(lái)譯.糾纏態(tài)：物理世界第一迷.上海：上?？萍嘉墨I(xiàn)出版社，2008-7.

［8］E.SchrAodinger.Die gegenwartige Situation in der Quantenmechanik（TheCurrent Situation in Quantum Mechanics）.Naturwissenschaften，1935，23：807-812.

［9］M.A.Nielsen and I.L.Chuang.Quantum computation and quantum information.Beijing：Higher Education Press，2003.

［10］C.H.Bennett and S.J.Wiesner.Communication via one-and two particle operators on Einstein-Podolsky-Rosen states.Physical Review Letters，1992，69：2881.

［11］C.H.Bennett，G.Brassard，C.Crepeau，R.Jozsa，A.Peres and W.K.Wootters.Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels Physical Review Letters，1993，70：1895.

［12］D.Bouwmeester，J.W.Pan，K.Mattle，et al.Experimental quantum teleportation.Nature，1997，390：575-579.

［13］溫巧燕，郭奮卓，朱甫臣.量子保密通信協(xié)議的設(shè)計(jì)與分析.北京：科學(xué)出版社，2009，6.

［14］Jane Qiu.Quantum communications leap out of the lab.Nature，2014，508：4 4.

［15］Aram W.Harrow.Why now is the right time to study quantum computing arXiv：1501.00011.

Quantum Computation and Quantum Information；the Brief History of Development；Basic Concept；Basic Characteristics；Basic Principles

The Introduction of Quantum Computation and Quantum Information

WANG Bang-hai，GONG Hong-bo
（School of Computer Science and Technology，Guangdong University of Technology，Guangzhou 510006）

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61272013）

1007-1423（2015）22-0018-05

10.3969/j.issn.1007-1423.2015.22.004

王幫海（1974-），男，副教授，博士，研究方向?yàn)榕d趣為量子計(jì)算與量子信息

2015-07-30

2015-08-05

介紹量子計(jì)算與量子信息的產(chǎn)生背景、發(fā)展簡(jiǎn)史，量子比特與量子門的數(shù)學(xué)描述以及它們與物理概念之間的關(guān)系。介紹量子并行基礎(chǔ)的線性疊加、量子力學(xué)獨(dú)特資源的糾纏及其應(yīng)用。介紹量子密碼無(wú)條件安全的理論基礎(chǔ)、發(fā)展歷史，量子信息學(xué)研究、量子計(jì)算機(jī)實(shí)現(xiàn)的現(xiàn)狀，并對(duì)未來(lái)作展望。

量子計(jì)算與量子信息；發(fā)展簡(jiǎn)史；基本概念；基本特性；基本原理

龔洪波（1989-），男，在讀碩士研究生，研究方向?yàn)榱孔佑?jì)算與量子信息

Introduces the background and the brief history of quantum computation and quantum information，describes the mathematical description of qubits and quantum gates and the relation between the mathematical description and their physical concepts.Introduces the linear superposition principle，which is the foundation of parallel computation，and quantum entanglement which is the unique property of quantum mechanics，and its application.Introduces the theory foundation of unconditional security of quantum cryptography and its history，introduces the current situation of the research on quantum information theory and the implement of quantum computer，and the future perspective of quantum computation and quantum information.