量子計算機理論概述

陳靈生

浙江廣電集團，浙江 杭州 310005

1 經典計算機與Moore定律

所謂經典計算機就是指目前在廣泛使用的電子計算機，之所以稱為經典計算機，是因為現在有了量子計算機的概念。毫無疑問，經典計算機在廣泛的使用領域取得了巨大的成功，很難想象那個行業能離得開計算機。

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

2 量子計算機概念的提出

計算機是執行計算任務的機器，它的本質是一個物理系統，計算過程本質上是個物理過程，量子計算機在本質上就是一個量子力學系統[2]。

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

由于量子態的幺正演化只存在于理想的孤立系統中，但在實際中，量子系統不可避免地和周圍環境發生相互作用，表現為量子計算中的噪聲干擾，導致量子計算很容易出錯。同時人們也不清楚，量子計算是否優于經典計算，所以量子計算一開始只停留在理論上可行的階段。

3 量子計算

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

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

其中α和β是復系數，滿足歸一化條件

這就是量子態的疊加原理。

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

如果量子計算機對2n這個一般態進行計算，就相當于對個基矢態同時進行計算，這就是量子計算的并行性。

與經典計算機中的邏輯門相對應，量子信息處理的基本操作元件是量子邏輯門。從數學的觀點看，量子邏輯門就是幺正矩陣或是幺正矩陣的組合，對量子態實施幺正變換就實現了對量子態所表達的數據的計算。

如果對任意維的Hilbert空間態（即量子態）的幺正變換，都可以通過一個邏輯門的組合來實現，那么這個邏輯門就是一個通用邏輯門。對于量子計算的通用邏輯門組，就是所謂的Deutsch門。Deutsch證明任意維Hilbert空間的幺正變換的量子計算網絡都可以用這個門的組合構造出來。這樣從理論上來說，可以像用經典邏輯門構建經典計算機一樣，用量子邏輯門構建量子計算機。

量子計算中還可利用的一個資源就是所謂的量子糾纏。比如雙量子比特系統處于態

這就是一個糾纏態。在這個特殊的態中，復合系統（雙量子比特）的態是完全確定的，但其中每個子系統（單個量子比特）的態是不確定的。同時兩個子系統之間存在著不可分割的聯系，表現為對其中任何一個子系統的測量會引起另一個子系統態的瞬時改變，不管兩個子系統相距有多遠。目前，人們可以利用量子糾纏實現隱形傳態，即利用兩地共享的量子糾纏對，把其中一地的未知量子態傳輸到另一地，卻不需要傳送這個量子比特本身。還可以利用量子糾纏實現超密編碼，即用一個量子比特位傳送兩個比特的經典信息。

4 量子計算機的實現與挑戰

經典計算機的實現方法比較統一，都是以大規模集成電路為基礎，采用Von Neumann的體系結構。然而，目前提出的量子計算機的實現方法則五花八門，不同學科的研究人員都從自己的研究領域出發，提出不同的實現方法。從理論上說，只要滿足量子計算所需的條件，任何實現方法都是可行的。目前已經提出的量子計算機的物理實現方案有:核磁共振量子計算機、離子阱量子計算機、中性原子量子計算機、光量子量子計算機、超導量子計算機等[2]。

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

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

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

[2]李承祖，陳平形，梁林梅，戴宏毅.量子計算機研究(上):原理和物理實現[M].科學出版社，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]趙生妹，鄭寶玉.量子信息處理技術[M].北京郵電大學出版社，2010.