量子计算复杂性理论综述  

Overview of Quantum Computation Complexity Theory

作　　者：张焕国[1] 毛少武[1] 吴万青[2] 吴朔媚[3] 刘金会[1] 王后珍[1] 贾建卫[1] 

机构地区：[1]武汉大学计算机学院空天信息安全与可信计算教育部重点实验室,武汉430072 [2]河北大学计算机科学与技术学院,河北保定017002 [3]石家庄学院计算机系,石家庄050035

出　　处：《计算机学报》2016年第12期2403-2428,共26页Chinese Journal of Computers

基　　金：国家自然科学基金(61303212;61202386);国家自然科学基金重点项目(61332019);国家"九七三"重点基础研究发展规划项目基金(2014CB340600)资助~~

摘　　要：量子计算复杂性理论是量子计算机科学的基础理论之一,对量子环境下的算法设计和问题求解具有指导意义.因此,该文对量子计算复杂性理论进行了综述.首先,介绍了各种量子图灵机模型及它们之间的关系.其次,量子计算复杂性是指在量子环境下对于某个问题求解的困难程度,包含问题复杂性、算法复杂性等.于是,该文介绍了量子问题复杂性、量子线路复杂性、量子算法复杂性,并且介绍了量子基本运算和Shor算法的优化实现.第三,格被看做是一种具有周期性结构的n维点空间集合.格密码有很多优势,包括具有抗量子计算的潜力,格算法具有简单易实现、高效性、可并行性特点,格密码已经被证明在最坏条件下和平均条件下具有同等的安全性.因此该文介绍了格的困难问题,以及主要的格密码方案现状.最后,对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望.The quantum computation complexity theory is one of the basic theories of quantum computer science, and it has guiding significance for the designing and solving some problems under the environment of quantum algorithms. Therefore, in this paper, the quantum computation complexity theory is reviewed. Firstly, this paper introduce the relationships between quantum Turing machine model and classical Turing model. Secondly, due to the quantum computational complexity is the degree of difficulty under the quantum environment for problem solving, including the complexity of the problem, the complexity of the algorithm and so on, this paper describes the quantum complexity of the problem, quantum circuit complexity, the complexity of quantum algorithms, and introduces the basic optimization for quantum computation and Shor algorithm. Thirdly, the lattice has n-dimensional periodic structure in space. Lattice based cryptography has many advantages, including post-quantum computation potential, lattice algorithm is simple, efficient, parallel and easy to implement, lattice cryptography has been shown to have equal safety under the worst conditions and average conditions. This paper describes some difficult problems about lattice, and the status of the main lattice cryptography scheme. Finally, the prospect about the cipher design and analysis of some important issues worthy of study and quantum computing environments is given.

关 键 词：量子计算 量子图灵机 量子计算复杂性 量子线路 量子环境下的密码 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]