基于量子逻辑的图灵机及其通用性

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.     

量子逻辑的发展及其理论基础

量子信息与量子计算的出现是信息科学发展的必然选择。介绍量子逻辑的发展历史、研究现状以及建立在Hilbert封闭子空间基础上的正交模格相关的理论基础和几个open问题。在此基础上,介绍量子计算的巨大计算能力的源泉,展望量子逻辑的可能研究方向。     

逻辑推理机制中的分配律

分配律在经典逻辑推理机制中具有核心地位。量子逻辑不再具有经典逻辑中的分配律,从而也失去了经典逻辑推理机制,因此量子逻辑是否可称为逻辑备受人们质疑。指出了希尔伯特空间闭子空间刻画量子逻辑的不足,并深层次地分析了经典逻辑推理机制的内涵,利用正交模律取代经典逻辑中的分配律,可以实现量子逻辑的推理能力。最后,通过范畴理论中伴随函子的概念重新审视逻辑推理机制,使经典逻辑推理机制推广到更广泛的逻辑领域中。     

Job-Shop调度问题的量子蚁群算法求解*

针对最小化最大完工时间的作业车间调度问题,提出了一种量子蚁群调度算法.该算法结合了量子计算中量子旋转门的量子信息和蚁群寻优的特点,通过作业车间调度问题的析取图表示,将原问题转换为求解析取图的关动路径,并利用量子蚁群算法进行求解.采用该算法对作业车间调度问题的基准数据进行测试,仿真结果表明了该算法的可行性和有效性.     

量子Harr小波变换及其逻辑实现

由于量子计算相比于经典计算的突出优越性,量子小波变换的实现对于小波变换的理论完善和实际应用具有重要的意义.在给出了正移置换矩阵的量子逻辑线路后,运用矩阵扩展Kronecker积,基于W-H变换和正移置换矩阵对Harr小波矩阵进行了分解,给出了相应的数学表达式和量子逻辑线路.并对其实现复杂度和物理实现可能性进行了分析.     

两硬币量子游走模型中的相干动力学

量子游走是量子计算的重要模型,而多硬币量子游走模型由于在量子通讯协议中表现突出也越来越受到人们的关注.量子相干不仅可以刻画量子态的特点,也可以反映量子演化过程的性质.主要对一维圆上两硬币量子游走模型的量子相干性进行了分析.一方面,讨论了初始量子态和硬币算子的选取对量子相干的影响.当硬币算子为Hadamard算子且初态只要在位置子空间上是均衡叠加态,整个量子游走演化过程是具有周期性的,且量子相干仅依赖于步数和圆上顶点的个数;当初始态是均衡叠加态而对硬币算子没有任何限制时,量子相干的演化也极具规律性.另一方面,发现在利用量子游走实现完美状态转移(perfect state transfer)的过程中,硬币算子的选取直接影响量子相干的值.最后,探讨了2种量子游走模型之间的等价性,并基于此指出了其在量子隐形传输(quantum teleportation)中的应用和改进的可能性.     

概率逻辑系统是与集合代数同态的布尔代数

联结词的本质是命题的运算,只有对所有命题都适用的真值函数才能用于定义联结词.概率逻辑中由于命题的内涵相关性,任何[0,1]上的函数都不能完全适用于任意命题的运算,概率逻辑的联结词不能定义成真值函数.各种算子可以作为一种计算方法使用和研究,但不能代表一个逻辑系统研究系统的性质.概率逻辑系统是概率空间的逻辑表示,是与概率空间中的事件域(集合代数)同态的布尔代数.用事件域上的集合函数精确定义各种联结词,与经典二值逻辑相容,与事实相符,能够在经典逻辑框架内实现概率命题演算.     

量子计算的表象无关性探讨

大因数分解和数据检索量子算法的提出带来了量子计算与量子信息的研究高潮。由于量子计算具有并行性、不可克隆性及量子态的不可测性,使得量子信息及量子计算在某些方面具有传统计算所无法比拟的优势。量子的态空间作为一个完备的Hilbert空间,在定义了内积和范数并赋予相应的物理意义后,就构成了理论意义上的量子计算系统。该文抽象了量子系统的本质,描述了量子计算及遵循的计算规则以及如何实现量子信息表示和进行信息的处理与测量,从理论上阐述了量子态系统迁移的线性同构和等距同构,说明了量子计算与量子信息的研究与具体的量子表象空间无关。     

基于量子逻辑的确定型正则文法

基于量子逻辑的文法理论是量子计算模型的一个重要研究方向.给出了基于量子逻辑的确定型正则文法的概念,证明了基于量子逻辑的确定型正则文法与基于量子逻辑的确定型自动机的等价性.利用此等价性,给出了量子确定正则语言的代数刻画和层次刻画,并得到量子确定正则语言关于正则运算的封闭性.     

基于标记Büchi自动机的时态描述逻辑ALC-LTL模型检测

时态描述逻辑将描述逻辑的刻画能力引入到命题时态逻辑中,适合于在语义Web环境下对相关系统的时态性质进行刻画.为了对这些时态性质进行高效的验证,在ALC-LTL的基础上研究了时态描述逻辑的模型检测问题.一方面,使用时态描述逻辑ALC-LTL公式来表示待验证的时态规范;另一方面,在对系统建模时借助描述逻辑ALC对领域知识进行刻画.针对上述扩展后得到的模型检测问题,提出了基于自动机的ALC-LTL模型检测算法.模型检测算法由3个阶段组成:首先将时态规范的否定形式和系统模型分别构造成标记büchi自动机;接下来构造这两个自动机的乘积自动机,并将关于ALC的推理机制融入到乘积自动机的构造过程中;最后对该乘积自动机进行判空检测.与LTL模型检测相比,时态描述逻辑ALC-LTL的模型检测引入了描述逻辑的刻画和推理机制,可以在语义Web环境下对语义Web服务等复杂系统的时态性质进行刻画和验证.     

Markov property in quantum logic: A reflection

A possible way of the Markov property introduction within the framework of the orthomodular quantum logic, which is commonly used as the calculus model for quantum mechanics is presented in this paper. The presented work follows the logical line rather than any physical interpretation in the framework of quantum mechanics. The basic algebraic structure, which is used as a model for noncompatible random events is an orthomodular lattice. On the orthomodular lattice, a dynamical structure is introduced coupled with mappings which have similar properties as s_n-maps on the orthomodular lattice. This construction leads to the definition of an L-process with the Markov property on the orthomodular lattice.     

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路.而且运行速度远远超过其他算法·实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.     

An overview of quantum computation models: quantum automata

Quantum automata, as theoretical models of quantum computers, include quantum finite automata (QFA), quantum sequential machines (QSM), quantum pushdown automata (QPDA), quantum Turing machines (QTM), quantum cellular automata (QCA), and the others, for example, automata theory based on quantum logic (orthomodular lattice-valued automata). In this paper, we try to outline a basic progress in the research on these models, focusing on QFA, QSM, QPDA, QTM, and orthomodular lattice-valued automata. Also, other models closely relative to them are mentioned. In particular, based on the existing results in the literature, we finally address a number of problems to be studied in future.     

An overview of quantum computation models: quantum automata

Quantum automata, as theoretical models of quantum computers, include quantum finite automata (QFA), quantum sequential machines (QSM), quantum pushdown automata (QPDA), quantum Turing machines (QTM), quantum cellular automata (QCA), and the others, for example, automata theory based on quantum logic (orthomodular lattice-valued automata). In this paper, we try to outline a basic progress in the research on these models, focusing on QFA, QSM, QPDA, QTM, and orthomodular lattice-valued automata. Also, other models closely relative to them are mentioned. In particular, based on the existing results in the literature, we finally address a number of problems to be studied in future.     

量子可逆逻辑电路综合的快速算法研究

可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.     

基于位运算的量子可逆逻辑电路快速综合算法

量子可逆逻辑电路是构建量子计算机的基本单元.本文结合可逆逻辑电路综合的多种算法,根据可逆逻辑电路综合的本质是置换问题,巧妙应用位运算构造高效完备的Hash函数,提出了基于Hash表的新颖高效的量子可逆逻辑电路综合算法,可使用多种量子门,以极高的效率生成最优的量子可逆逻辑电路,从理论上实现制造量子电路的成本最低.按照国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其它算法.实验结果表明,该算法按最小长度标准综合电路的平均速度是目前最好结果的69.8倍.     

A review on quantum search algorithms

The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It is evident from the early invented quantum algorithms such as Deutsch’s algorithm, Deutsch–Jozsa algorithm and its variation as Bernstein–Vazirani algorithm, Simon algorithm, Shor’s algorithms, etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science because it comes as a subroutine in many important algorithms. Quantum database search of Grover achieves the task of finding the target element in an unsorted database in a time quadratically faster than the classical computer. We review Grover’s quantum search algorithms for a singe and multiple target elements in a database. The partial search algorithm of Grover and Radhakrishnan and its optimization by Korepin called GRK algorithm are also discussed.     

Notes on automata theory based on quantum logic

The main results are as follows: (1) it deals with a number of basic operations (concatenation, Kleene closure, homomorphism, complement); (2) due to a condition imposed on the implication operator for discussing some basic issues in orthomodular lattice-valued automata, this condition is investigated in detail, and it is discovered that all the relatively reasonable five implication operators in quantum logic do not satisfy this condition, and that one of the five implications satisfies such a condition iff the truth-value lattice is indeed a Boolean algebra; (3) it deals further with orthomodular lattice-valued successor and source operators; (4) an example is provided, implying that some negative results obtained in the literature may still hold in some typical orthomodular lattice-valued automata.     

Filter-based resolution principle for lattice-valued propositional logic LP(X)

As one of most powerful approaches in automated reasoning, resolution principle has been introduced to non-classical logics, such as many-valued logic. However, most of the existing works are limited to the chain-type truth-value fields. Lattice-valued logic is a kind of important non-classical logic, which can be applied to describe and handle incomparability by the incomparable elements in its truth-value field. In this paper, a filter-based resolution principle for the lattice-valued propositional logic LP(X) based on lattice implication algebra is presented, where filter of the truth-value field being a lattice implication algebra is taken as the criterion for measuring the satisfiability of a lattice-valued logical formula. The notions and properties of lattice implication algebra, filter of lattice implication algebra, and the lattice-valued propositional logic LP(X) are given firstly. The definitions and structures of two kinds of lattice-valued logical formulae, i.e., the simple generalized clauses and complex generalized clauses, are presented then. Finally, the filter-based resolution principle is given and after that the soundness theorem and weak completeness theorems for the presented approach are proved.