量子资讯浅谈

《量子资讯浅谈》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、量子資訊淺談蘇正耀國家高速電腦中心zsu@nchc.gov.tw量子資訊學是近年來快速成長的領域。限於時問，本文僅對早期幾個主要的發展，做最淺顯的介紹。夢想與驚喜始自第一個電子計算機開始運轉，構想能夠超越傳統所謂TuringMachines的計算模型，便是許多科學家努力的夢想。美國阿岡國家實驗室的PaulBenioff是第一位提出槪念'11，認爲利用量子物理的二態系統模擬數位0與1，可以設計出更有效能的計算工具。此槪念稍後又經Feynman的引中°，使得有更多的物理學家注意到量子力學與計算科學之間可能的關聯。直到1985年，

2、在英國牛津的物理學家DavidDeutsch發表的一篇論文裡'"，所謂QuantumChurch—TuringMachines才正式開始略具數學型式。但此論文中所提示的量子計算範例，則過於簡易且不甚實際。到了1994年，BellLab的應用數學家PeterShor，於當年IEEE基礎計算理論年會發表突破性工作-快速整數因數分解方法（現今已被稱爲ShortAlgorithm）4,，量子計算的潛在應用實力便迅速引起廣泛的注意。因爲如果能對任意極大的整數快速作質數分解，就可以破解目前普遍採用的RSA密碼系統。以傳統已知最快的方法對

3、整數N做質數分解，其計算的複雜度（Complexity）是此整數位數（logN）的指數函數；此難以突破的鉅額計算複雜度保証了密碼系統的安全性。Shor的方法卻可將此複雜度降爲多項式函數（雖然僅是機率性的），使得快速破解RSA密碼系統成爲可能。此工作所引起的震撼不難想像，自94年後有關量子計算、量子通訊或所謂量子資訊學的論文便疾速增加，也開始吸引大暈硏究經费的投入（特別是來自軍方與工業界）。目前在美國、歐洲、日本以及屮國大陸，已經有許多專爲此新領域而成立的硏究團隊或硏究機構。而Shor本人則於98年柏林舉行的國際數學大會，與A

4、ndrewWiles（費馬最後定理的証明者）一同獲獎表揚（雖然不是費爾茲獎，但與其對等）。平行與糾纏量子計算機的實現，不是爲了取代傳統的計算機，實際上也無法取代。一個有效的量子計算方法，其成功在於巧妙的結合本身特徵優勢，以及可在傳統計算機快速執行的古典技巧，然後在特定極困難問題上擊敗已知的傳統方法。這裡所指的特徵優勢主要有二即所謂的量子平行（QuantumParallelism）與暈子纏糸吉（QuantumEntanglement）。暈子平行簡而言之，就是只需n個運算（四變換，UnitaryTransforms），就可以準備

5、出2n個可能狀態，雖然這2“個狀態是以線性組合的方式結爲一個狀態；所以口然也可以再一起通過另外一個變換，就相當於同時對此才個狀態做了該變換。而爲準備此2“個狀態，也只需要n個量子位元（Qubits，由二態量子系統來實現）即可。量子纏結指的是兩個或更多的量子系統彼此關聯，因而使得某些物理量無法由單一或少數的系統獨立決定。此纏結特徵幾乎在所有的量子運算中口然產生，也是計算所以加速的原因之一；但因爲是口然產生，故往往不在過程中特別強調，待稍後範例再來說明量子纏結極其特殊的作用。一個量子計算的過程可簡單視爲將所有可能的2“個輸入（M

6、puts），以線性組合的方式“儲放”在n個量子位元上，再加上運算過程中輔助用的m個量子位元（m

7、子力學一般）而非絶定性的（deterministic）-分離與追尋Shor整數因數分解方法的成功，在j於精巧的結合了古典數論技巧與量子傅利葉變換（QFT，QuantumFourierTransform）。這裡的古典數論技巧主要指的是計算一特定模數函數的週期（故須引用傅利葉變換來求得此週期），再利用孰知的輾轉相除法即可獲得該整數N的因數。此技巧早在70年代已被應用在數論與資訊科學硏究上/，本身即是機率性的方法。而量子傅利葉變換是由IBM的Coppersmith首先給出'，數學上可視爲快速傅利葉變換（FFT»FastFourie

8、rTransform）的量子計算版本（量子計算中基本的HadamardTransform即是2-pointFFT）。由於量子平行的特性，使得變換的複雜度由FFT的0（NlogN）降爲QFT的O（logNlogN）。雖然是機率性的方法，但由於每次嘗試的計算複雜度已大爲降低，所以整體而言仍保証