2012-03-06 | 编辑：文\信息技术部
近日，由国家数学与交叉中心陆汝钤院士、尚云课题组在量子计算理论方面取得重要进展。部分研究成果已在Theoretical Computer Science （34页长文）,Mathematical Structures in Computer Science等国际刊物和会议上发表。其中，基于Unsharp量子逻辑的有穷自动机和下推自动机方面的结果被匿名审稿人评价为：“非常有趣”，“是对量子逻辑框架下计算理论的一个重要贡献。”基于Unsharp量子逻辑的图灵机被8th Quantum Physics and Logics评审认为“The fact that there are ENTM for undecidable languages is a surprising result.”
自Von Neumann 在1936年创立量子逻辑以来，绝大多数有关量子逻辑和量子信息处理的研究都是针对封闭量子系统，而且标准代数模型是正交模格，只能反映投影算子值（PV）测量，其元素必须满足非矛盾律
和排中律
，但是不满足分配律
及其对偶定律）。对应的逻辑称为sharp量子逻辑。但是，封闭量子系统仅仅是量子系统的一个特例。近年来，研究人员逐渐将注意力投向范围更广、结构更复杂的开放量子系统（如一个更大量子系统的子系统），测量变为正算子值（POV）测量，相应的量子逻辑也发展成为unsharp量子逻辑，并且逻辑不仅不满足分配律，还不满足非矛盾律和排中律，因此正交模格不再是这类量子系统的代数模型。
在经典的可计算性理论中，自动机理论起着非常重要的作用。有穷自动机、下推自动机、线性有界自动机和图灵机构成了一个完整的计算体系，而且已经被证明分别等价于Chomsky的3型、2型、1型和0型文法。在这个自动机体系之上，计算机科学家们已经获得了一套丰富的理论体系，该理论体系一直指导着计算机科学中的可计算性理论研究，并且在实际应用（例如编译技术）中发挥着重要作用。
一个很自然的问题是：在量子情况下是否存在这样一个计算体系？如果有的话，我们应该如何去建立它？它和经典的计算体系又有何本质不同？
应明生教授等人基于Sharp量子逻辑及其代数模型—正交模格，系统地建立了基于sharp 量子逻辑的量子有穷自动机理论和量子下推自动机理论。然而，他们并没有研究基于同一逻辑的量子线性有界自动机理论和量子图灵机理论。因此，仅就Sharp量子自动机而言，该领域也存在着很大的空白。更重要的是，至今国内外还没有人开展过基于Unsharp量子逻辑的量子自动机理论研究。为了建立基于Unsharp量子逻辑的计算理论，需要找到恰当的代数模型，该模型应该能够反映开量子系统的非分配性、非交换性和非排中性等特点，并且能够作为Unsharp量子自动机的支撑代数模型，使得在这些广泛的条件下仍能获得有意义的结果。
他们课题组围绕这个问题，以Unsharp量子逻辑为背景，开展了系统的研究。主要结果是获得了基于Unsharp量子逻辑的，包括3、2、1、0型量子自动机在内的一套完整量子计算体系。我们获得了Unsharp量子自动机的许多特殊性质，证明它们不仅与经典自动机的对应性质有本质区别，而且与Sharp量子自动机的对应性质有本质区别。
为了建立基于Unsharp量子逻辑的计算理论，需要找到恰当的代数模型，该模型应该能够反映开量子系统的非分配性、非交换性和非排中性等特点，并且能够作为Unsharp量子自动机的支撑代数模型，使得在这些广泛的条件下仍能获得有意义的结果。
他们发现格序QMV代数和扩张的格序Effect代数可以作为主要的Unsharp量子结构，以此为基础我们系统地建立了基于Unsharp 量子逻辑的计算理论。主要包括：基于Unsharp 量子逻辑的有穷自动机和下推自动机理论，基于Unsharp 量子逻辑的图灵机和线性有界自动机理论。通过深入系统的研究，我们发现了这些Unsharp量子自动机的一系列不寻常的性质，主要包括：
确定型和非确定型量子有穷自动机不等价，量子有穷自动机和量子正则文法不等价；量子下推自动机和量子上下文无关文法不等价；量子线性有界自动机和量子上下文有关文法不等价。而他们之间的等价需要凭借的逻辑退化为多值逻辑，在物理实现上要求对应的可观测量之间是Coexistent。
确定型和非确定型量子图灵机不等价；非确定型量子图灵机比经典图灵机功能强大，可以识别递归可枚举语言和递归可枚举语言的补；基于量子逻辑的通用图灵机不存在。
上述各种量子自动机的语言对补均不封闭。
他们进一步研究了“是否存在最简结构的量子逻辑模型”这一重要问题，并且建立了一种新的Unsharp量子结构—Weak QMV代数，结构上弱于目前应用较多的QMV模型，性质上可以完全替代QMV模型，并且同样可以建立起基于一套完整的自动机体系的量子计算理论。
上述结果显然是与经典计算理论的实质区别，而所有这一切均来源于在Unsharp量子逻辑中分配律、排中律和无矛盾律不成立。
