资源描述：
《量子计算浅谈》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、量子計算淺談文廐正耀摘要量子計算是量子資訊科學領域重要的一環，本文對其早期主要的發展做淺顯的介紹。、平行與糾一、夢想與驚喜始自第一個電子計算機開始運轉,構想能夠超越傳統所謂TuringMachines的計算模型,便是許多科學家努力的夢想。美國阿岡國家實驗室的PaulBenioff是第一位提出槪念*認爲利用量了物理的二態系統模擬數位0與1，可以設計出更有效能的計算工具。此槪念稍後又經Feynman的引申，使得有更多的物理學家注意到量子力學與計算科學之問可能的關聯。直到1985年，在英國牛津的物理學家DavidDeutsch發表的一篇
2、論文裡，所謂QuantumChurch—TuringMachines才正式開始略具數學雛型，但此論文中所提示的量子計算範例則過於簡易。到了1994年,BellLab的應用數學家PeterShor，於當年IEEE基礎計算理論年會發表突破性工作一快速整數因數分解方法（現今已被稱爲Shor'sAlgorithm），量子計算的潛在應用實力便迅速引起廣泛的注意。因爲如果能對任意極大的整數快速作質數分解，就可以破解目前普遍採用的RSA密碼系統。以傳統已知最快的方法對整數艸做負數分解，其計算的複雜度（Complexity，也就是所須計算的步數）
3、是此整數位數（logN）的指數函數;此難以突破的鉅額計算複雜度提供了密碼系統的安全性。Shor的方法卻可將此複雜度降爲多項式函數（雖然僅是機率性的），使得快速破解RSA密碼系統成爲可能。此工作所引起的震撼不難想像，自94年後有關量子計算、量子通訊或所謂量子資訊學的論文便疾速增加，也開始吸引大量硏究經費的投入（特別是來自軍方與工業界）。目前在美國、歐洲、日本以及屮國大陸，已經有許多專爲此新領域而成立的硏究團隊或硏究機構。而Shor本人則於98年柏林舉行的國際數學大會，與AndrewWiles（費馬最後定理的證明者）一同獲獎表揚（雖然
4、不是費爾茲獎，但仍被視爲與其對等）。量子計算機的實現，不是爲了取代傳統的計算機，實際上也無法取代。一個有效的量子計算方法，其成功在於巧妙的結合本身特徵優勢，以及可在傳統計算機快速執行的古典技巧，然後在特定極困難問題上超越已知的傳統方法。這裡所指的特徵優勢主要有二一即所謂的量子平行（QuantumParallelism)與量子纏結(QuantumEntanglement)。量子平行簡而言之，就是只需n個運算(酉變換，或譯么正變換，UnitaryTransforms)，就可以準備出2”個可能狀態，雖然這2”個狀態是以線性組合的方式結爲
5、一個狀態；所以自然也可以再一起通過另外一個變換，就相當於同時對此2"個狀態做了該變換。而爲準備此2"個狀態，也只需要刀個量子位元(Qubits，由二態量子系統來實現)即可。量子纏結由酢丁格首先以德文Verschrankung出，原意爲兩手臂的交纏。而量子纏結的物理涵義是指兩個或更多的量子系統間存在特定的所謂非局域性關聯，因而使得某些物理量無法由單一或少數的系統獨立決定。此纏結特徵幾乎在所有的量了運算中自然產生，也可能是計算所以加速的原因之一：但因爲是自然產生，故往往不在計算過程中特別強調，待稍後其他範例再來說明量子纏結極其特殊的作
6、用。一個量子計算的過程可簡單視爲將所有可能的2”個輸入(inputs)，以線性組合的方式“儲放”在刀個量子位元上，再加上運算過程中輔助用的刃個量了位元(加<“⑺)，Q是某一個多項式函數)的資料，一起通過適當數冃(此數冃也是刀的某一個多項式函數)經特別設計的酉變換，之後2”個outputs即同時現，雖然仍舊以某種線性組合的方式儲放在數個量子位元上。如何從這輸出的線性組合態“萃取”一即測量其中一個或數個量子位元一正確的答案，則完全取決於運算過程中酉變換的選擇與組合設計。至此可以看出量子計算能獲致止確答案，往往是機率性(probabil
7、isticornondeterministic5如同量子力學一般)而非決定性的(deterministic)°三、分離與追尋Shor整數因數分解方法的成功，在於精巧的結合了古典數論技巧與量子傅利葉變換(QFT，QuantumFourierTransform)。這裡的古典數論技巧主要指的是計算模數函數fN,a(x)=ax(modN)的週期；河是待被分解的整數，8是任意選取比N小且與河互質的整數，而才是由0開始的整數。求得此函數的週期厂後，就利用孰知的輾轉相除法來計算gcd(/2±i,N)，也就是±i與N的最大公約數，則至少其中之一將
8、是N的因數。舉例說明，假設N=5，任意選取a=7，則當x=(),1,2,3,4,…，/©)=1,7,4,13,1,…，(他£足碼已省略)，所以此函數的週期r=4。計算72±1=50,48與15的最大公因數分別爲5和3，恰好都是15的因數。此技巧早
