基于量子逻辑的不确定性计算模型及其应用研究

Quantum computing is an important research area of the computer science, while, the computing model of quantum computation is one of the key scientific issues in this field. The purpose of this study are integrate the computation theory based on quantum logic: including establish the theory of context-free grammar, finite tree automaton, ω-regular expression, Müller automaton, Müller tree automaton and the related research results of classical automata into the frame of quantum logic setting by using semantic analysis. ..i) By dint of refine and modify the extended subset constructions, we will present the pumping lemma of quantum context-free languages, which decide whether an quantum language is an quantum context-free language or not, and also obtain the relevant equivalent algebraic characterizations of finite tree automata, Müller automata and Müller tree automata based on quantum logic...ii) With the help of introduce the concept of the monadic second-order quantum logic , based on the “levelization ” processing techniques ,we will give the equivalent monadic second-order quantum logic description of those corresponding quantum automata, which expanding the fundamental Büchi theorem to quantum setting...iii) By means of provide the notions of ω-star-free quantum ω-language and ω-aperiodic quantum ω-language respectively, and we will establish the first-order description of ω-regular quantum languages recognized by a given quantum Müller automaton, and also obtain a sorting scheme of quantum Müller recognizable ω-regular languages. ..iv) As for applications, we will preliminarily investigate the state transition system and the bisimulation theory in quantum logic, which intend to construct the theory of model checking using automata based on quantum logic.

量子计算是计算机科学领域重要的研究方向，其中量子计算模型是其关键的科学问题之一。本项目拟采用语义分析方法，完善基于量子逻辑的计算理论：建立量子逻辑框架下的上下文无关文法、有限树自动机、ω-正则表达式、Müller自动机、Rabin自动机和Müller树自动机等理论。i) 通过细化和改造广义子集构造方法，给出量子上下文无关语言的泵引理；建立量子逻辑框架下的有限树自动机、Müller自动机和Müller树自动机的相关等价代数刻画。ii) 通过引入单体二阶量子逻辑的概念，利用“层次化”处理技巧，给出其等价单体二阶量子逻辑描述，深化和推广量子逻辑框架下的Büchi基本定理。iii) 通过引入ω-星自由和ω-非周期的量子ω-语言，给出Müller自动机识别语言的一阶逻辑描述和一种有效分类方法。iv) 作为应用，初步探讨量子逻辑框架下的状态转换系统和互模拟理论，为基于自动机的量子模型检测理论做准备。

量子计算是计算机科学领域重要的研究方向，其中量子计算模型是其关键的科学问题之一。本项目利用语义分析方法，主要针对不满足分配律的量子逻辑框架下计算模型理论进行了深入研究，在此取得比较本质和深刻的成果，并初步将成果应用于多值模型检测和形式化验证领域。第一，深化和推广了量子上下文无关文法理论，得到了更广泛的结果，建立了取值于赋值幺半群的量化下推自动机和量化上下文无关文法理论，证明了在双幺赋值幺半群框架下以终状态与以空栈方式识别语言的量化下推自动机彼此等价，研究了量化上下文无关语言对于正则运算的封闭性，给出了量化下推自动机与量化上下文无关文法相互等价的条件。第二，有效扩充了量子逻辑框架下的Müller自动机理论。第三，重点研究了量子逻辑框架下的有穷树自动机理论，给出了以深度优先与广度优先方式定义的两种量子有穷正则树语言等价的充要条件，借助广义子集构造技术，证明了自底向上的量子非确定型与确定型有穷树自动机相互等价，通过层次化处理技巧，得到了量子有穷树语言的代数刻画与层次刻画，这些构成了量子有穷树自动机的等价代数刻画，藉此得到了即使量子逻辑本身不满足分配律，但量子有穷正则树语言在正则运算下仍封闭的结论。第四，结合空闭包的技术，讨论清楚了不同类型的量子有穷树自动机间的关系，给出了量子有穷正则树语言的泵引理，通过引入量子有穷正则树表达式，阐明了量子有穷正则树语言的Kleene定理，这些深化和推广了经典树自动机方面的基本定理至量子逻辑框架下。第五，作为初步应用，丰富了多值逻辑、多值逻辑框架下的模型检测和形式化验证理论。第六、扩展了量子纠缠理论。本项目结题之后，将剩余经费继续研究量子计算模型的逻辑刻画和应用。