几类非确定型量子程序的终止验证

摘要

程序验证是保证程序正确性的关键技术。由于经典世界和量子世界的本质不同，经典程序验证的技术和工具不能直接应用到量子系统。而量子程序设计语言是描述量子系统的一种新的形式化模型，量子程序的验证问题就显得更为迫切和必要。本文首先讨论了量子通讯中常用的比特翻转、相位翻转、去极化、幅值阻尼、相位阻尼等信道作为特殊的非确定型量子程序从计算基态开始运行时的可达集合和终止集合等程序验证问题。其次，把上述五种量子程序两两组合组成非确定型量子程序，根据这五种量子程序的可达集合之相似点，最终合并成三种非确定型量子程序，重点讨论了这三种非确定型量子程序从计算基态开始运行时的终止和发散等程序验证问题。研究表明：这三种非确定型量子程序从计算基态0开始运行时都是终止的；而从计算基态1开始运行时：比特翻转信道和去极化信道组成的非确定型量子程序的终止和发散与分别刻画它们的两个参数有关；比特翻转信道和相位翻转信道组成的非确定型量子程序的终止和发散只与刻画比特翻转信道的参数有关；幅值阻尼信道和相位阻尼信道组成的非确定型量子程序是发散的，其发散条件与刻画量子信道的两个参数都没有关系。本文的结果可以为量子信息安全中量子通讯协议的验证提供理论和技术支持。%Program verification is the key technology to ensure the correctness of the program.However,due to essen-tial differences of the classical and quantum world,classical program verification techniques and tools cannot be applied di-rectly to the quantum system.Since quantum programming language is a new formal model of quantum system,the verifica-tion problem of quantum program is more urgent and necessary.We investigate the program verification for the reachable set and the terminating set of specific nondeterministic quantum program described respectively by bit flip channel,phase flip channel,depolarizing channel,amplitude damping channel and phase damping channel starting from computational basic states in quantum communication systems.Then,we combine pairwise the above five quantum programs into nondeterminis-tic quantum programs,and merge these nondeterministic quantum programs into three nondeterministic quantum programs in terms of the similarities of the reachable set of five quantum programs,and discuss the problem for termination and diver-gence of these three nondeterministic quantum programs starting from computational basic states.The results shows that these three nondeterministic quantum programs starting from computational basic state 0 are terminated,while starting from com-putational basic state 1 ,the termination and the divergence of nondeterministic quantum program consisted by bit flip channel and depolarizing channel relates to the two parameters describing two quantum channels,the termination and the divergence of nondeterministic quantum program consisted by bit flip channel and phase flip channel relates to one parameter describing bit flip channel,and nondeterministic quantum program consisted by amplitude damping channel and phase damping channel is divergence without the two parameters describing quantum channel.And the results provide theoretical and technical sup-port for verification of quantum communication protocol in quantum information security.