从1900年普朗克提出量子假设至今,量子理论历经了百多年的发展。量子理论不但让人们更深刻地认识了微观世界,也与其它领域交融而产生了新的学科。量子计算正是量子物理、数学以及计算机科学相融合的充满活力的新兴交叉学科。　　 量子计算是应用量子力学效应来进行有效计算的新的计算方式,在过去的十几年里这种新的计算方式吸引了大批的物理学家、数学家和计算机科学家。在量子物理方面,人们集中于量子态纠缠、量子退相干、量子噪声等理论研究。同时在量子实验中物理学家也在寻找能有效地实现量子操作的材料和技术,如离子阱、核磁共振、光量子、量子点、半导体以及超导材料等等。在数学上,人们则努力于研究量子编码、设计新的量子算法。在计算机科学领域,人们致力于设计量子程序语言、量子算法,研究量子计算复杂性以及量子计算模型。　　 “量子计算机”的设想最早由著名物理学家Feymann提出[56,57]。早在上世纪八十年代,因为无法用经典计算机来有效地模拟量子实验系统,Feymann提出了在计算中运用量子效应的想法,也就是设计一种量子力学机器。但Feymann没有给出量子计算机的具体构造。1985年Deutsch[37]第一次给出了量子图灵机的明确定义,并且展示了量子计算特有的量子并行技术。1989年Deutsch[38]又把经典的逻辑电路模型推广到了量子线路模型,后来其他人又发展出各种各样的量子计算模型。　　 ·1996年Grover[83]最早考虑了分布式量子计算机。分布式量子计算机可以看成是量子网络的推广。一般的量子计算模型,如量子图灵机,都假设硬件上可以存在任意多个量子比特。但在有些实际情况中(例如超导量子计算),单个量子处理器上的量子比特数目受到硬件的限制,这使得一般的量子计算模型不再适用,而分布式量子计算模型则可以适合于这样的情形。2005年前后Yimsiriwattana与Lomonaco[216,217]设计了分布式的Shor算法。　　 ·作为元胞自动机的量子推广,1988年Gr(o)ssing[81]提出了量子元胞自动机。2007年Perez.Delgado和Cheung[165]提出了更广泛的局域量子元胞自动机,解决了GrSssing的量子元胞自动机中元胞间不能交互的问题。　　 ·从提高量子计算的可靠性出发,1997年Kitaev[109]将量子信息与拓扑自由度相结合,提出了拓扑量子计算机。拓扑量子计算机具有内在的容错能力,目前的研究集中于寻找用于计算的非阿贝尔任意子。　　 ·为了更易于物理实现,1999年Gottesman与Chuang[77]提出了只需要单量子门和Bell基测量的基于传输的量子计算机。2001年Raussendorf与Briegel更进一步,提出了只需要单量子操作的单向量子计算机[173]。这两种模型降低了量子计算物理实现的难度。2007年Raussendorf等人[171]研究了单向量子计算机上的拓扑容错计算,进一步提高了计算可靠性。　　 ·以上模型都是基于传统的量子门和线路。2001年Farhi等人[52,53]基于量子物理中的“绝热定理”提出了新颖的绝热量子计算。2010年Harris等人[95]已经在实验室中成功实现了复杂多量子位绝热计算。　　 ·为了进行可扩展的量子计算,1997年Loss与DiVincenzo[3l]提出了固态自旋量子计算机。之后也出现了众多固态自旋量子计算机的实现方案[7,32,64,100,105,114,120,140,167,189,193]。　　 量子计算也面临着诸多困难,有理论上的也有物理实现上的。物理实现上的主要障碍是纠错和量子退相干问题。克服退相干的一种方法是从技术上采用新的材料和先进的实验方法,例如用精细的操控延长退相干时间,或创造更好的实验条件尽量降低系统外噪声的干扰。在实验上对退相干的研究已经有了很大的进展。2008年来自普林斯顿大学、牛津大学和加州伯克利实验室的科学家小组已经可实现在原子核中存储量子比特超过1秒。2009年来自中美的科学家小组用激光大大延缓了退相干过程[213]。2011年8月南加州大学Takahashi小组首次实现了对复杂实验系统中的环境退相干的预测和控制[196]。克服退相干的另一种方法是采取量子编码的方式利用冗余的量子位来达到可靠量子计算的目的[8,22,43,106,110,123-125,191,192],不过这种方法将消耗更多的量子比特资源。最近的2012年美国物理学会年度会议上IBM的研究人员宣布,他们在试验中利用耶鲁大学提出的3维超导量子比特[160],将量子比特维持量子态的时间延长到了100微秒[179],满足进行有效纠错的最小时间。这也许意味着量子计算技术将应用阶段。量子计算在理论上的困难主要在于受到量子力学规则的限制,例如量子力学中的不可克隆原理使得在计算中不再能随意地复制任意未知态;量子系统在测量时的塌缩将不可逆地丢失信息,而复制和读出数据正是电子计算机最常用的操作！不论采用上述哪种量子计算模型,这些问题都不可避免。这些困难都反映出量子计算与经典计算的区别。　　 量子计算的实验研究取得了长足进展,而量子计算的理论研究开始得更早。早在1936年,G.Birkhoff和J.vonNeumann就提出了量子逻辑的概念,也就是将刻画量子系统的命题等同于其相空间(Hilbert空间)的闭子空间,从而抽象出量子系统的逻辑。在这个量子逻辑中,一个命题不能同时为真又为假。但是进一步的研究显示在开放量子系统中,一个命题可以既真又假,即不满足“非矛盾律”,这样的量子逻辑又称为不分明量子逻辑,而将原来vonNeumann的量子逻辑称为分明量子逻辑。　　 分明量子逻辑(sharpquantumlogic)的主要代数模型是正交模格,它反映量子系统的分明可观测量的性质;而不分明量子逻辑(unsharpquantumlogic)的主要代数模型是effect代数(effectalgebra)、QMV代数和MV代数等多种量子结构,它们反映量子系统的不分明可观测量的性质。分明量子逻辑与不分明量子逻辑在代数上的主要区别是,前者满足非矛盾律而后者没有非矛盾律。从量子逻辑的角度建立计算理论就是首先把逻辑命题的真值取为量子代数结构中的元素,然后在这样的量子代数结构上建立起一套自动机理论。　　 本文中我们主要研究基于不分明量子逻辑的计算理论。在这个理论中,我们使用格序QMV代数1(或者扩展的格序effect代数)作为各种自动机运行的取值格,并称之为ε值。本文内容分为两部分,分别是基于不分明量子逻辑的计算理论和量子结构自身性质的研究。主要创新点有以下几个方面:　　 1.定义了不分明量子逻辑上的有限状态自动机及其语言和正则表达式。采用深度优先和宽度优先两种方式定义自动机识别的语言。我们发现在这两种识别的方式下,Kleene定理的成立都依赖分配律;泵引理在有限的条件下成立。尤其与经典有限状态自动机和分明量子逻辑上的有限状态自动机不同的是,ε值正则语言的补不再是ε值正则语言。　　 2.定义了不分明量子逻辑上的下推自动机和上下文无关文法。主要证明了1QuantumManyValuedAlgebra.在深度宽度两种方式下ε值上下文无关文法与乔姆斯基范式、格雷巴赫范式以及ε值下推自动机的等价性。　　 3.考虑了不分明量子逻辑上的图灵机及其语言和文法。与经典图灵机的性质明显不同的是:确定型ε值图灵机与非确定型ε值图灵机不等价:而且在格序QMV代数是无限集的情况下,通用ε值图灵机也不存在;不论是按深度优先规则还是宽度优先规则,其ε值语言在(正交)补运算下都不封闭。　　 4.定义了分明量子逻辑(取值格为正交模格,称为(L)值)和不分明量子逻辑上的线性有界自动机。同样证明了ε值线性有界自动机的语言在(正交)补运算下不封闭,这显然与经典线性有界自动机有着实质的不同。最后我们证明了ε((L)值)线性有界自动机与ε值((L)值)上卞文相关文法在深度优先下的等价性,在宽度优先规则下这种等价性的存在需要ε(L)退化为MV代数(布尔代数)。　　 5.提出了一种新的量子代数结构——弱QMV代数,它保留了与QMV代数相似的序关系、运算的单调性等大部分性质。证明了coupled双含幺半群与格序弱QMV代数存在对应关系。继而在这种coupled双含幺半群的基础上得到强coupkd双含幺半群,并证明它与格序QMV代数有对应关系。　　 6.我们把著名的vonNeumann代数和正交模格(分明量子逻辑)的分解推广到QMV代数上。证明了当且仅当某个幂等元是中心元时,可以把QMV代数分解为两个区间的直积或直和,这两个区间分别以此幂等元和它的正交补为界。