第六章量子计算模型.pdfVIP

第六章 量子計算模型 蔡錫鈞 國立交通大學資訊工程學系 6.1引言 (Preamble) 計算機科學自肇始以來 即以研究問題的可計算性及演算法的效率為職志， 。由於 計算機的製造及運作方式各異 ，需有一理論性的模型來統一進行探討。杜林機乃 是由 AlanTuring提出 ，可有效描述任意計算機的計算行為的數學模型 。杜林機 的模型雖然抽象 ，但是一般計算機上的演算法 ，均可有效轉化在杜林機上進行運 算 。AlonzoChurch及 Turing因此提出 邱池杜林理論 ，其中提出杜林機即是所 有可有效計算的問題的模型 。多年以來此一假設仍無法找出反例因此吾人均相， 信 杜林機確為正確描述計算過程的模型。 在杜林機的模型中 ，「計算 」的動作乃是依照古典物理的原則進行 。二十世紀八 十年代以來開始有物理學者提出疑問是否可以利用量子力學的特性可以建造超， 越杜林機限制的計算機(Feynmann 1982)。此一問題在 1994 年由 Peter修爾 (Shor 1994)給出肯定的解答 。質因子分解在傳統計算機上至今仍找不到有效的 演算法可進行運算 ，但是藉由基於量子力學進行運算的計算機 (量子計算 ) ，此 問題可被有效地計算得出解答 。在此之後 ，陸陸續續地產生許多結果指出量子計 算的確可以超越傳統 杜林機的限制 ，更快速地計算出問題的解答 。 本章將會介紹兩類量子計算的模型:量子杜林機 與量子電路，在介紹此二模型之 前 ，先介紹傳統杜林機的模型以及量子力學的基本原則 ，以導引讀者入門。 6.2杜林機(Turingmachine) 6.2.1杜林機基本構造 杜林機(以下簡稱TM)是由 AlanTuring所提出用來描繪計算過程的數學模型 。 它的主要構成和一般計算機的結構類似，具有處理單元以及記憶單元。利用一組 設定好的控制程序 ，TM可以進行運算工作 。 TM的主要構成共有 : 1 記憶單元 TM的記憶單元可以想像成是一條磁帶 磁帶， 上有一連串的儲存格，利用一組 固定的 字符(alphabet記載著資料) 。磁帶的長度不受限制 ，可以是無限長 。 這是 TM和一般計算機最大的不同之處 ，因為一般計算機的記憶體不論其硬 體能力如何 ，總是有限的 。磁帶 上記錄著運算過程開始前輸入的資料、運算 途中可能暫時產生的資料 ，和運算終止時輸出的資料 。 2 處理單元 TM的 處理單元可以想像成是一個讀寫頭 讀寫頭指向， 磁帶中某個儲存位置 ， 讀寫頭可以讀取該位置之資料 ，或是寫入新值 ，並可在磁帶 上進行左右的移 動 。讀寫頭中另有一暫存器記錄 TM當下所處的狀態 (狀態)。 3 控制程序 TM的控制程序負責決定讀寫頭在不同狀態下遇到不同資料時所進行的操 作 ，讀寫頭可以對磁帶寫入資料 ，或是移動位置至左右兩邊之儲存格 ，也可 更改 TM的狀態 。整個圖機的運算過程可以說是由控制程序完全決定 。 圖 6.1TM的磁帶及讀寫頭 上圖是一個簡單的TM的範例圖 ，磁帶 上的儲存格自0開始向無限大延伸 ， 讀寫頭一開始指向磁帶位置 0的儲存格 ，並處於狀態q0 。 圖 6.2TM運算過程 上圖是TM的運算過程的範例 ，原本讀寫頭指向儲存格 2並處於狀態q0 ，控 制程序依照狀態q 及儲存格上的資料 a ，決定將該格資料更改為b ，並將讀 0 寫頭左移至儲存格 1，同時將狀態改為 q1 。 吾人綜合前述內容 ，將TM正式定義如下。 定義6.1(杜林機TM) 一部TM是一個三元組 M (Q,,) ，其中  Q是一有限非空集合 ，表示