【作者】 林添荣；

【导师】 蒋建民；

【作者基本信息】 福建师范大学 ， 计算机软件与理论， 2011， 硕士

【摘要】 量子计算是一门交叉于数学、物理与计算机科学的前沿学科,具有令人期待的发展前景.量子计算的研究主要分为对量子计算模型、量子计算复杂性和量子算法的研究.目前,广泛引起学者兴趣的量子计算模型主要有量子图灵机(quantum Turing machines)、量子电路(quantum circuit)和量子有限自动机(quantum finite automata)特别地,量子有限自动机可被看作是基于量子力学原理的最为简单的计算模型.目前,有多种不同的量子有限自动机被学者提出,这些量子有限自动机在更好地理解量子计算方面扮演着不可或缺的角色.在经典计算领域,有限自动机等价性判定是一个基本且重要的问题,它实质上是对有限自动机的分类问题.基于这种观点,对各种量子有限自动机进行分类在量子计算研究中有同等的地位.本文主要研究两种类型的量子有限自动机等价性问题,主要有以下工作：·研究了测量多次的单向量子有限自动机(MM-1QFA)等价性问题,从MM-1QFA的标准字函数出发,构造了另一个与之等价的字函数.通过这个字函数,证明了定义在相同字母表上的两个MM-1QFAs等价当且仅当它们是n2/1+n2/2-1-等价,中n1和n2是所讨论的两个MM-1QFAs的状态数目；·研究了多字符量子有限自动机(multi-letter QFA)的等价性问题.改进了现有的结论,即：将多字符量子有限自动机等价判定的上界(n1+n2)4+k-1(在字母表为∑={σ}的情形)二次方优地改进到(n1+n2)2+k-1；然后讨论了在字母表为一般情形下(即∑={σ1,σ2,…,σm},2≤m<∞),多字符量子有限自动机等价问题,证明了存在一个正整数z,使得两个多字符量子有限自动机等价当且仅当它们满足z-等价.更多还原

【Abstract】 Quantum computing is a research field at the current frontiers of computing, which halfway between mathematics, physics and computer science. Quantum fi-nite automata can be viewed as the simplest theoretical models based on quantum mechanism. The aim of studing quantum finite automata is to explore the power of quantum computation and the characterizations of quantum computation fully. Thus far, variant quantum finite automata have been proposed. Studying of such quantum finite automata pay an indispensable role in further understanding quan-tum computation. In the theory of classical computation, determining the equiva-lence of finite automata is a foundational and important issue. In essentialness, it is concerned with the classification of finite automata. Base on this point of view, the classification of various kinds of quantum finite automata takes on the same position. Concerning these,we make the following contribution.●Starting from the standard word function of MM-1QFAs, we construct a new word function which equivalent to the standard one, then we show that two MM-1QFAs over the same input alphabet are equivalent if and only if they are n12+n22-1-equivalent, where n1 and n2 are the numbers of states of the two MM-1QFAs, respectively;●We then investigated the equivalence issue of multi-letter quantum finite au-tomata (multi-letter QFA). To be specific, in the case that the input alphabet has one element, i.e.,∑={σ}, we show that two multi-letter QFAs are equiv-alent if and only if they are (n1+n2)2+κ-1-equivalent; Then, we show that there exists an integer z such that two multi-letter QFAs are equivalent if and only if they are z-equivalent.更多还原