半量子计算模型与密码通信中的若干问题

Quantum resources are precious and it is more difficult to process quantum information than classical information processing. Therefore, we hope use as less quantum operations as possible to surpass classical information processing in essence. In this project, by combining quantum properties and classical components, we study some issues concerning quantum computational models and quantum cryptography communication. More specifically, we investigate the computational ability and state complexity of two-way and one-way finite automata with quantum and classical states, and compare their numbers of states for recognizing the same languages with quantum automata, probabilistic automata, and classical automata. In addition, we establish quantum Buchi automata and study their operation properties and the decidability of if the language recognized by quantum Buchi automata is empty. This should provide a kind of tools for quantum model-checking. On the other hand, we design a semi-quantum secret sharing protocol without entnaglement and semi-quantum (k,n)-threshold secret sharing protocol, and then investigate their security. Furthermore, we consider their security under the imperfect conditions such as nonideal resource of quantum bit, noise channel, channel loss, and measuring methods in practice etc.

鉴于量子资源是宝贵的且处理量子信息比处理经典信息更难，所以我们希望用最少的量子操作而达到本质上超越经典信息处理的目的。本项目结合量子与经典的处理方法研究量子计算模型与量子密码通信中的若干问题。主要包括研究带量子和经典状态的双向及单向自动机的计算能力和状态复杂性，并在识别相同语言时，与相应的概率自动机和经典自动机比较状态数的大小关系。建立量子Buchi自动机，并讨论有关的运算性质和其识别的语言的空性判定问题，为量子模型检测提供一定的理论基础。另一方面，设计不带纠缠的半量子秘密共享协议和半量子(k,n)阈值秘密共享协议，并讨论其安全性，进一步考察半量子密码通信协议在不完美的量子比特资源、噪声信道、信道损失和实际测量方法等情形下的安全性。

本项目结合量子与经典的处理方法研究量子计算模型与量子密码通信中的若干问题。 主要包括两大方面：一方面研究带量子和经典状态的双向及单向自动机的计算能力和状态复杂性，并与相应的概率自动机和经典自动机比较状态数的大小关系。另一方面设计新的半量子密码协议，并讨论在不完美的量子比特资源、噪声信道、信道损失和实际测量方法等情形下的安全性。提出了一类分布式半量子算法解决相位估计问题，这个算法的时间复杂性有指数级的改进；刻画了所有精确量子一次查询复杂性的布尔函数，这为研究刻画一般k次查询复杂性的问题提供了思路；证明了一个单量子半量子密钥分配协议的在非理想情形时的安全性。在国际计算机科学著名学术期刊 Information and Computation, Journal of Computer and System Sciences, Theoretical Computer Science, Information Processing Letters, Quantum Information and Computation, Quantum Information Processing, International Journal of Foundation of Computer Science, RAIRO-Theoretical Informatics and Applications, Mathematical Structures in Computer Science, IEEE Transactions on Fuzzy Systems, International Journal of Theoretical Physics, Science in China等发表28篇学术论文。