量子计算模型相关问题的研究

量子计算模型的计算能力，等价性，最小化，复杂性等问题具有重要的理论意义和潜在的应用价值。本项目主要研究以下几个问题：（1）混态量子有限自动机的计算能力，等价性问题，最小化问题；（2）与量子有限自动机所识别语言相关的几个判定性问题：空问题，成员归属问题，全集问题；（3）量子有限自动机（QFA）的状态复杂性问题；特别地，我们希望在量子通信复杂性与QFA的状态复杂性之间建立紧密的联系；（4）利用量子电路模型与基于测量的量子计算模型之间的转换关系，讨论量子电路的深度复杂性。

在本项目的资助下，完成了以下方面的研究：1.解决了混态量子有限自动机的计算能力及等价性判定等问题，证明该模型只能识别正则语言，并证明其等价性问题是可判定的。2.解决了量子及模糊有限自动机的状态最小化问题，证明以上问题均是可判定的。其中量子自动机的状态最小化问题自2000 年提出以来，一直未得到解决。3. 考察了量子自动机的状态复杂性，得到一些有趣的结论。特别是考察了半量子自动机（即含量子态又含经典态的一类模型）的状态复杂性，证明存在一些语言，半量子自动机要比对应的经典模型指数级节省状态。4.建立了一个新的半量子有限自动机模型，并就其计算能力，等价性，最小化等方面进行了深入的刻画。5. 设计了一个不借助量子纠缠态的半量子秘密共享协议，并分析了其安全性。以上成果发表在Theoretical Computer Science，Information and Computation，Journal of computer and system sciences , EEE Transactions on Fuzzy Systems，Journal of Physics A：Mathematical and Theoretical 等国际知名期，共计8篇，另外还有三篇在投论文。获得两项后续项目资助，培养在读研究生3名。除了研究计划中有关基于测量的量子计算的问题还未有较成熟的结果，其他计划研究内容均涉及到。另外，还解决了研究计划之外的两个问题：模糊有限自动机的最小化以及半量子秘密共享。总的来说，本项目的研究基本达到预期目标。