量子有限自动机等价性判定研究

摘要

量子计算是一门交叉于数学、物理与计算机科学的前沿学科,具有令人期待的发展前景.量子计算的研究主要分为对量子计算模型、量子计算复杂性和量子算法的研究.目前,广泛引起学者兴趣的量子计算模型主要有量子图灵机(quantumTuring machines)、量子电路(quantum circuit)和量子有限自动机(quantum finiteautomata).特别地,量子有限自动机可被看作是基于量子力学原理的最为简单的计算模型.目前,有多种不同的量子有限自动机被学者提出,这些量子有限自动机在更好地理解量子计算方面扮演着不可或缺的角色.
　　 在经典计算领域,有限自动机等价性判定是一个基本且重要的问题,它实质上是对有限自动机的分类问题.基于这种观点,对各种量子有限自动机进行分类在量子计算研究中有同等的地位.本文主要研究两种类型的量子有限自动机等价性问题,主要有以下工作:
　　 ·研究了测量多次的单向量子有限自动机(MM-1QFA)等价性问题,从MM-1QFA的标准字函数出发,构造了另一个与之等价的字函数.通过这个字函数,证明了定义在相同字母表上的两个MM-1QFAs等价当且仅当它们是n21+n22-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-等价.