臺灣國際科展

確定有限狀態自動機與量子有限狀態自動機之間的轉換與比較

科展類別
臺灣國際科展作品
屆次
2017年
科別
電腦科學與資訊工程
得獎情形
二等獎
學校名稱
臺北市立第一女子高級中學
指導老師
江介宏;黃芳蘭
作者
官欣;陳穎
關鍵字
自動機,量子計算,資料轉換

摘要或動機

量子計算的效率相較傳統計算有指數級成長。然而此領域中多數研究皆專注於量子計算的性質本身,鮮少討論如何將傳統環境中的既有資訊轉換至量子環境下。一旦量子電腦實現,受量子效應限制,傳統資料多半不能相容於量子環境中。因此,本研究的目的是發想出一種系統性的演算法以確實跨越量子資訊與傳統資訊之間資料結構的藩籬。我們選擇的計算機模型是確定有限狀態自動機(Deterministic Finite Automaton,簡稱DFA)。 本研究由自動機的轉移矩陣(Transition Matrix)及量子環境要求的可逆性(Reversibility)出發,自傳統DFA一步步轉換至量子有限狀態自動機(Quantum Finite Automaton,簡稱QFA)並進行優化。最終,我們定義出一種新的QFA模型(QDFA)能在量子環境下運行,具有增大的字母表(Alphabet Set)但功能完全等價於DFA(能辨認正則語言)。本研究獨創的演算法的時間複雜度為O(C×N2)。


「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
確定有限狀態自動機與量子有限狀態自動機之間的轉換與比較 1 MB Adobe Reader(Pdf)檔案