文献类型：期刊文章

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

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

出　　处：《计算机学报》

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

年　　份：2016

卷　　号：39

期　　号：12

起止页码：2403-2428

语　　种：中文

收录情况：BDHX、BDHX2014、CSA、CSA-PROQEUST、CSCD、CSCD2015_2016、EI(收录号：20165203163166)、IC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：量子计算复杂性理论是量子计算机科学的基础理论之一,对量子环境下的算法设计和问题求解具有指导意义.因此,该文对量子计算复杂性理论进行了综述.首先,介绍了各种量子图灵机模型及它们之间的关系.其次,量子计算复杂性是指在量子环境下对于某个问题求解的困难程度,包含问题复杂性、算法复杂性等.于是,该文介绍了量子问题复杂性、量子线路复杂性、量子算法复杂性,并且介绍了量子基本运算和Shor算法的优化实现.第三,格被看做是一种具有周期性结构的n维点空间集合.格密码有很多优势,包括具有抗量子计算的潜力,格算法具有简单易实现、高效性、可并行性特点,格密码已经被证明在最坏条件下和平均条件下具有同等的安全性.因此该文介绍了格的困难问题,以及主要的格密码方案现状.最后,对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望.

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

分 类 号：TP301]