量子計算與量子信息簡介

王幫海，龔洪波

（廣東工業(yè)大學計算機學院，廣州　510006）

量子計算與量子信息簡介

王幫海，龔洪波

（廣東工業(yè)大學計算機學院，廣州510006）

0　引言

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

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

1　量子信息學發(fā)展簡史

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

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

2　量子比特與量子門

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

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

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

3　量子基本特性及其應用

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

（1）量子線性疊加

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

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

（2）量子糾纏及其應用

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

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

（1）量子超密編碼

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

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

4　量子基本原理及其應用

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

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

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

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

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

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

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

5　發(fā)展與展望

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

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

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

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

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

［2］王幫海.基于糾纏破壞信道與糾纏目擊者的可分標準研究.博士論文：中山大學計算機系，2011，6.

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

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

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

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

［7］A.D.Aczel.Entanglement：The greatest mystery in physics.John Wileyand Sons Ltd.2002.莊星來譯.糾纏態(tài)：物理世界第一迷.上海：上?？萍嘉墨I出版社，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é)議的設計與分析.北京：科學出版社，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）

國家自然科學基金資助項目（No.61272013）

1007-1423（2015）22-0018-05

10.3969/j.issn.1007-1423.2015.22.004

王幫海（1974-），男，副教授，博士，研究方向為興趣為量子計算與量子信息

2015-07-30

2015-08-05

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

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

龔洪波（1989-），男，在讀碩士研究生，研究方向為量子計算與量子信息

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.