量子計算與量子信息簡介

王幫海，龔洪波

（廣東工業大學計算機學院，廣州　510006）

量子計算與量子信息簡介

王幫海，龔洪波

（廣東工業大學計算機學院，廣州510006）

0　引言

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

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

1　量子信息學發展簡史

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

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

2　量子比特與量子門

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

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

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

3　量子基本特性及其應用

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

（1）量子線性疊加

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

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

（2）量子糾纏及其應用

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

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

（1）量子超密編碼

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

（2）量子隱形傳態

4　量子基本原理及其應用

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

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

定理2：無法可靠區分兩個非正交量子態。

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

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

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

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

5　發展與展望

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

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

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

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

［1］佐川弘幸，吉田宣章著.突破經典信息科學的極限――量子信息論.宋鶴山，宋天譯.大連理工大學出版社，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.莊星來譯.糾纏態：物理世界第一迷.上海：上海科技文獻出版社，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］溫巧燕，郭奮卓，朱甫臣.量子保密通信協議的設計與分析.北京：科學出版社，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

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

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

龔洪波（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.