量子有限自動(dòng)機(jī)等價(jià)性判定研究.pdf

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

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

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