量子有限自動機等價性判定研究.pdf

1、量子計算是一門交叉于數(shù)學、物理與計算機科學的前沿學科,具有令人期待的發(fā)展前景.量子計算的研究主要分為對量子計算模型、量子計算復雜性和量子算法的研究.目前,廣泛引起學者興趣的量子計算模型主要有量子圖靈機(quantumTuring machines)、量子電路(quantum circuit)和量子有限自動機(quantum finiteautomata).特別地,量子有限自動機可被看作是基于量子力學原理的最為簡單的計算模型.目前,有多種

2、不同的量子有限自動機被學者提出,這些量子有限自動機在更好地理解量子計算方面扮演著不可或缺的角色.
　　 在經(jīng)典計算領域,有限自動機等價性判定是一個基本且重要的問題,它實質(zhì)上是對有限自動機的分類問題.基于這種觀點,對各種量子有限自動機進行分類在量子計算研究中有同等的地位.本文主要研究兩種類型的量子有限自動機等價性問題,主要有以下工作:
　　 ·研究了測量多次的單向量子有限自動機(MM-1QFA)等價性問題,從MM-1QFA

3、的標準字函數(shù)出發(fā),構造了另一個與之等價的字函數(shù).通過這個字函數(shù),證明了定義在相同字母表上的兩個MM-1QFAs等價當且僅當它們是n21+n22-1-等價,中n1和n2是所討論的兩個MM-1QFAs的狀態(tài)數(shù)目；
　　 ·研究了多字符量子有限自動機(multi-letter QFA)的等價性問題.改進了現(xiàn)有的結論,即:將多字符量子有限自動機等價判定的上界(n1+n2)4+k-1(在字母表為∑=｛σ｝的情形)二次方優(yōu)地改進到(n1+n