基於量子邏輯的不確定性計算模型及其套用研究

《基於量子邏輯的不確定性計算模型及其套用研究》是依託陝西師範大學，由韓召偉擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於量子邏輯的不確定性計算模型及其套用研究
• 項目類別：青年科學基金項目
• 項目負責人：韓召偉
• 依託單位：陝西師範大學

項目摘要

量子計算是計算機科學領域重要的研究方向，其中量子計算模型是其關鍵的科學問題之一。本項目擬採用語義分析方法，完善基於量子邏輯的計算理論：建立量子邏輯框架下的上下文無關文法、有限樹自動機、ω-正則表達式、Müller自動機、Rabin自動機和Müller樹自動機等理論。(i) 通過細化和改造廣義子集構造方法，給出量子上下文無關語言的泵引理；建立量子邏輯框架下的有限樹自動機、Müller自動機和Müller樹自動機的相關等價代數刻畫。(ii) 通過引入單體二階量子邏輯的概念，利用“層次化”處理技巧，給出其等價單體二階量子邏輯描述，深化和推廣量子邏輯框架下的Büchi基本定理。(iii) 通過引入ω-星自由和ω-非周期的量子ω-語言，給出Müller自動機識別語言的一階邏輯描述和一種有效分類方法。(iv) 作為套用，初步探討量子邏輯框架下的狀態轉換系統和互模擬理論，為基於自動機的量子模型檢測理論做準備。

結題摘要

量子計算是計算機科學領域重要的研究方向，其中量子計算模型是其關鍵的科學問題之一。本項目利用語義分析方法，主要針對不滿足分配律的量子邏輯框架下計算模型理論進行了深入研究，在此取得比較本質和深刻的成果，並初步將成果套用於多值模型檢測和形式化驗證領域。第一，深化和推廣了量子上下文無關文法理論，得到了更廣泛的結果，建立了取值於賦值么半群的量化下推自動機和量化上下文無關文法理論，證明了在雙麼賦值么半群框架下以終狀態與以空棧方式識別語言的量化下推自動機彼此等價，研究了量化上下文無關語言對於正則運算的封閉性，給出了量化下推自動機與量化上下文無關文法相互等價的條件。第二，有效擴充了量子邏輯框架下的Müller自動機理論。第三，重點研究了量子邏輯框架下的有窮樹自動機理論，給出了以深度優先與廣度優先方式定義的兩種量子有窮正則樹語言等價的充要條件，藉助廣義子集構造技術，證明了自底向上的量子非確定型與確定型有窮樹自動機相互等價，通過層次化處理技巧，得到了量子有窮樹語言的代數刻畫與層次刻畫，這些構成了量子有窮樹自動機的等價代數刻畫，藉此得到了即使量子邏輯本身不滿足分配律，但量子有窮正則樹語言在正則運算下仍封閉的結論。第四，結合空閉包的技術，討論清楚了不同類型的量子有窮樹自動機間的關係，給出了量子有窮正則樹語言的泵引理，通過引入量子有窮正則樹表達式，闡明了量子有窮正則樹語言的Kleene定理，這些深化和推廣了經典樹自動機方面的基本定理至量子邏輯框架下。第五，作為初步套用，豐富了多值邏輯、多值邏輯框架下的模型檢測和形式化驗證理論。第六、擴展了量子糾纏理論。本項目結題之後，將剩餘經費繼續研究量子計算模型的邏輯刻畫和套用。