量子计算复杂性理论综述

资源描述

《量子计算复杂性理论综述》由会员分享，可在线阅读，更多相关《量子计算复杂性理论综述（26页珍藏版）》请在金锄头文库上搜索。

1、书书书第卷第期年月计算机学报收稿日期：；在线出版日期：本课题得到国家自然科学基金（，）、国家自然科学基金重点项目（）和国家“九七三”重点基础研究发展规划项目基金（）资助张焕国，男，年生，教授，主要研究领域为信息安全、密码学、可信计算等：毛少武，男，年生，博士研究生，主要研究方向为信息安全、密码学吴万青，男，年生，博士研究生，主要研究方向为信息安全、

2、量子密码吴朔媚，女，年生，讲师，主要研究方向为计算机密码刘金会，女，年生，博士研究生，主要研究方向为信息安全、密码学王后珍，男，年生，讲师，主要研究方向为信息安全、密码学贾建卫，男，年生，博士研究生，主要研究方向为信息安全、密码学量子计算复杂性理论综述张焕国）毛少武）吴万青）吴朔媚）刘金会）王后珍）贾建卫）（武汉大学计算机学院空天信息安全与可信计算教育部

3、重点实验室武汉）（河北大学计算机科学与技术学院河北保定）（石家庄学院计算机系石家庄）摘要量子计算复杂性理论是量子计算机科学的基础理论之一，对量子环境下的算法设计和问题求解具有指导意义因此，该文对量子计算复杂性理论进行了综述首先，介绍了各种量子图灵机模型及它们之间的关系其次，量子计算复杂性是指在量子环境下对于某个问题求解的

4、困难程度，包含问题复杂性、算法复杂性等于是，该文介绍了量子问题复杂性、量子线路复杂性、量子算法复杂性，并且介绍了量子基本运算和算法的优化实现第三，格被看做是一种具有周期性结构的狀维点空间集合格密码有很多优势，包括具有抗量子计算的潜力，格算法具有简单易实现、高效性、可并行性特点，格密码已经被证明在最坏条件下和平均条件下具有同等的安全

5、性因此该文介绍了格的困难问题，以及主要的格密码方案现状最后，对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望关键词量子计算；量子图灵机；量子计算复杂性；量子线路；量子环境下的密码中图法分类号犇犗犐号犗狏犲狉狏犻犲狑狅犳犙狌犪狀狋狌犿犆狅犿狆狌狋犪狋犻狅狀犆狅犿狆犾犲狓犻狋狔犜犺犲狅狉狔）））））））（犓犲

6、狔犔犪犫狅狉犪狋狅狉狔狅犳犛狆犪犮犲犐狀犳狅狉犿犪狋犻狅狀犛犲犮狌狉犻狋狔犪狀犱犜狉狌狊狋犲犱犆狅犿狆狌狋犻狀犵狅犳犕犻狀犻狊狋狉狔狅犳犈犱狌犮犪狋犻狅狀，犠狌犺犪狀犝狀犻狏犲狉狊犻狋狔，犠狌犺犪狀）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犎犲犫犲犻犝狀犻狏犲狉狊犻狋狔，犅犪狅犱犻狀犵，犎犲犫犲犻）

7、（犆狅犿狆狌狋犲狉犇犲狆犪狉狋犿犲狀狋，犛犺犻犼犻犪狕犺狌犪狀犵犝狀犻狏犲狉狊犻狋狔，犛犺犻犼犻犪狕犺狌犪狀犵）犃犫狊狋狉犪犮狋，，，，，，，，，，，，狀，，，，，，，犓犲狔狑狅狉犱狊；；；；引言目前随着量子和生物等新型信息科学的建立和发展，涌现出许多新的研究领域量子信息科学的研究和发展催生了量子计算机、量子通信和量子密码它们

8、的出现为量子信息理论研究和技术发展拓宽了范围促使了一些新的量子理论和量子算法出现例如，等人首次给出了量子计算的模型，指出量子计算在计算方面优于电子计算给出了称为算法的例子给出了一种标准搜索算法，复杂度是犗（槡狀）随后给出了分解大整数问题和求解离散对数问题的有效量子算法等人将算法扩展到交换群，提出了隐藏子群问题（）等人指出存在有

9、效的量子算法找到非交换群的正规子群等这些已知的量子算法大体上可以分为类：第类是基于量子变换的量子算法该算法实际将求周期函数的周期问题归结为隐藏子群问题例如，的因子分解算法和离散对数算法，这两个算法是对经典算法的指数加速；第类是量子数据库搜索算法例如，的量子搜索算法及其推广算法该算法的计算复杂性是经典算法的开方加速，目前已

10、经发展成为量子搜索算法体系；第类是量子仿真算法，即量子模拟系统这些量子算法的出现对经典公钥密码产生了严重的威胁，主要表现在：（）算法的作用相当于把密钥的长度减少一半，这对所有的密码都是一个威胁；（）算法对基于大整数分解和离散对数问题的公钥密码产生了严重的威胁，譬如、、密码等和指出在犽量子位的量子计算机上可以容易地求解犽比特

11、的椭圆曲线离散对数问题，其中犖犽槡犽犽对于整数因子分解问题，指出在犽位量子计算机上可以容易地分解犽比特的整数，其中犖犽据此分析，利用量子位量子计算机可以求解位椭圆曲线离散对数问题因此也就可破译位椭圆曲线密码利用量子位量子计算机就可以分解位的大合数因此就可以破译位的密码；（）算法的出现对基于交换群的密码产生了本质的威胁因此，凡是可

12、归结到上的公钥密码都不能抵抗量子计算的攻击可见量子算法的出现为密码分析提供了新的理论和工具除了在理论分析上取得了许多成果外，在量子计算机的物理实现上已经取得一些重要的成果在国际上，年月撰文指出加拿大公司推出世界上首台量子位商用量子计算机系统著名军火商洛克希德马丁公司以万美元台购买了用于战机分析，新武器开发和航天航空

13、器系统测试等年初，加拿大公司又推出量子位的谷歌公司以万美元台购买了用于加速信息搜索的速度和人工智能但是加拿大公司推出的系列量子计算机是专用型的量子计算机，不是通用型的，只能处理某些特定的问题年公司率先研制成功了的示例性通用量子计算机证明了量子计算机原理的正确性和可行性年月，撰文指出团队通过量子电路成功实现了冯诺依曼结

14、构的个量子位的量子计算机年在美国物理年会上公布声称找到了可以大规模提升量子计算机规模的一种关键技术年美国报告指出微软公司早在十年前就与加州大学圣巴巴拉分校合作开始研究量子计算机年月，科学家获得量子位的纠缠态远高于以前的量子位年月日谷歌公司宣布投资亿美元与的研究团队联合研制量子计算机综上所述，虽然量子计算机离大规模使用

15、还有很长的距离但是，一旦大规模的量子计算机成为现实，现有的许多公钥密码将不再安全量子计算时代我们使用什么密码，是摆在我国面前的一个十分紧迫的重大战略问题！这样就迫切需要研究能抵计算机学报年御量子计算的新型密码抗量子计算的密码主要包括以下几类：（）基于量子物理的量子密码；（）基于生物学的密码；（）基于量子计算不擅长计算的数学

16、问题构建的密码量子计算复杂性理论是量子密码体制安全性的理论基础，也是构造现代量子密码体制的理论依据它给出求解一个问题是容易还是困难的依据，并由此对问题和算法的复杂性进行分类，进而根据困难问题设计量子计算环境下的安全密码由于量子计算机具有并行性，所以它在许多方面具有比电子计算机更强大的计算能力这使得现在广泛应用的许多

17、密码在量子计算环境下将不再安全，，量子计算复杂性理论是量子计算机科学的基础理论之一，对量子环境下的算法设计和问题求解具有指导意义因此，量子计算复杂性理论成为量子环境下密码安全的理论基础本文对量子计算复杂性理论进行了综述介绍了各种量子图灵机模型及它们之间的关系，并进行了量子线路模型与量子图灵机的比较详细讨论了量子计算

18、复杂性，包括量子算法复杂性，问题复杂性和量子线路复杂性特别提出了一种新的量子计算数据复杂性最后，对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望经典复杂性理论在介绍量子复杂性之前，先简单地回顾一下经典的复杂性算法复杂性理论研究基于算法求解问题所要花费的资源消耗，包括时间、空间资源（比特数、带数、逻辑门数）等的

19、消耗通过考察求解某个问题的不同算法复杂程度来衡量问题的难易程度由此将问题划分为不同的类型，并对各种算法按其有效性进行分类在表中总结了常见的经典复杂性问题分类在图中给出了部分复杂性关系的一个简图图各种经典算法复杂性关系表经典复杂性分类经典复杂性分类定义确定型单带图灵机在多项式时间内可判定的语言类某个非确定型多项式时间图

20、灵机判定的语言类问题子集，可以通过多项式时间算法归约到一个问题上多项式时间的概率图灵机以严格大于的概率接收的语言非确定型图灵机在平均多项式时间内接收的语言概率图灵机在多项式时间和对数空间以严格大于的概率接收的语言多项式时间的概率图灵机以错误概率接收的语言类多项式时间非确定性图灵机以大于的概率接收的语言类存在

21、指数时间的确定性图灵机接收的语言类存在指数时间的非确定性图灵机接收的语言类算法是指可用来求解某一问题的过程称一个算法求解一个问题，是指该算法可应用到问题的任一例子，并保证总能找到该例子的一个解一个算法的有效性可以用执行该算法时所需的各种计算资源的量来度量最典型、也是最主要的资源是所需的运行时间和内存空间在复杂性研究

22、中，衡量一个算法的效果，最广泛采用的标准是求解问题所花费的时间，称为时间复杂性计算复杂性常用的符号犗（），狅（），（），（），（）利用这些记号可以将函数划分为不同的类在复杂性理论中，对如此定义的同一类型的不同函数往往不加以区分量子图灵机模型量子复杂性理论考虑的是在量子计算环境下评估解决某个问题的资源消耗情况而这些资源的评估都

23、是基于某个模型的这样的模型有量子图灵机模型、量子线路模型、量子查询模型、量子通信协议模型等本节主要介绍了量子图灵机模型利用量子图灵机模型，可以解释量子计算机求解的问题分类量子图灵机的讨论类似于经典的概率图灵机（）因此下面我们介绍一些量子图灵机的模型及它们之间的关系最早，指出经典图灵机不能有效模拟量子力学过程，需要发展量子

24、计算模型来模拟量子体系的演化阐述量子图灵机概念，并提出了量子计算复杂性理论基于此，和在数学上首次对量子计算模型给予严格的形式化描述量子图灵机模型（）设有限状态集犙，而期张焕国等：量子计算复杂性理论综述狇，狇犢，狇犖犙分别是初始状态，接受状态和拒绝状态设带中所有字符的一个有限集合，它包含输入字符表子集用表示中的字符所组成的所有有限长字符

25、串的集合，空白字符犫（）是量子状态转移函数，满足：犙犙，犆（）其中（狇，犪，犪，狇，犱）是格局在状态狇读取字符犪，沿方向犱，进入状态狇将读取字符犪转移函数指定了无限维空间的格局叠加态的线性映射犕（时间演化算子）随后，文献对该模型进行了微调，增加了一个静止的读写头设量子图灵机（）是一个七元组（犙，狇，狇犢，狇犖）量子状态转移函数满足：犙犙，狅，珚犆（）其中（狇，犪，犱）犙，（狇，犪，狇，犪，犱），珚犆应

26、为复数集的子集，其实部与虚部是多项式时间可计算的存在确定性多项式时间函数犳（狀）的算法精确计算复数的实部和虚部，满足犳（狀）狀，分别表示读写头移动方向狅代表读写头不移动它的工作原理如下：设犛是的格局且犛是有限线性组合上的满足欧几里德归一化条件的复内积空间，称犛中的每个元素为犕的一个叠加量子有限状态转移函数诱导一个时间演化算子犝犕：犛犛犕以格局犮起

27、始，当前状态为狆，且扫描标识符，下一动作犕将会被置为格局叠加：犻犻犮犻其中每个非零的犻都与一个量子转移函数（狇，犪，狇，犪，犱）对应，犮犻是向犮施行转化得到的新的格局通过线性时间演化算子犝犕可以将这种操作扩展到整个犛空间广义量子图灵机（）等人在年提出了广义图灵机的概念，定义如下：设四元组犕（犙，犎，），其中字母表犙是处理器格局，是包含空字符串的字母表，犎是希尔

28、伯特空间，是量子态的转移函数设?（犎）是希尔伯特空间犎密度算子的集合量子态的转移函数：?（犎）?（犎）的工作原理如下：给定格局犽犽犽犽，其中犽犽，犽且犽狇犽犃犽犻犽（狇犽犙，犃犽，犻犽犣），是希尔伯特空间犎的一组基所以这个转移函数是（）犽犽犽犽且犽，犽需要注意的是，如果是一个幺正算子犝那么犕（犙，犎，）可以规约到随机预言量子图灵机（）在年等人提出了随机预言量子图灵机有一个特

29、殊的查询纸带，除了非空白的单元外纸带的所有单元都是空白同时含有两个不同的内部状态矢量：先验查询状态狇狇和后验查询状态狇犪无论机器何时进行查询先验状态狇狇都开始查询若查询串是空的，则不操作且机器直接转到后验查询状态狇犪若查询串非空，查询串可写为狓犫，其中狓，犫，表示串联，这种情况下，调用谕示犃（狓）的结果将内部状态转到后验查询状态狇犪，然后查询纸带内

30、容从狓犫变化到狓犫犃（狓）除了查询纸带和内部控制外其他部分不发生变化容易发现，若给定初始值犫，即犫，则最终态为犃（狓）与经典的随机预言计算机一样，若给定初始犫犃（狓），则最终查询态为这表明调用谕示犃（狓）将重置靶比特为它的工作原理如下：当调用随机预言量子图灵机时，将酉变换犝作用在查询纸带目录狕上记作犝狕犝定义在可数无限维希尔伯特空间上，由二进制串，，

31、，，，，，，，组成其中表示空串对于谕示图灵机，一般的酉随机预言服从酉演化随机预言将输入映射到叠加态输出，不需要保长在犝狕中只有有限个基向量的振幅为同时犝，调用一个随机预言的结果可以通过进一步调用相同的随机预言进行复原另外，允许适当的干扰发生下面举了一个例子加以说明设图灵机的所有字符，犫，犫是空白符号，输入字符表子集，随机预言是一个酉

32、运算犗，作用于计算机上定义为狓狇犗狓狇犳（狓）（）其中狓是指标寄存器，是模加法，随机预言的量子比特狇，狇是单量子比特当犳（狓），则翻转；否则不变通过制备狓，应用随机预言，检查随机预言量子比特是否翻转到，来判断狓是否为搜索问题的一个解我们注意到有一些量子算法是带有随机预言模型的“ ” ，譬如算法、搜索算法、算法等这个量子谕示作为一个黑盒，不考虑输入的具体细节

33、在讨论这些问题的计算复杂性时需要构造谕示，并估计构造谕示需要的资源如果能构造这样谕示，称问题是可解的另外，计算机学报年并不是所有的量子算法都需要谕示在文献，中等人给出了一些不需要谕示的例子因此被视作带有随机预言模型“ ”的量子图灵机多带量子图灵机模型（）在年提出了多带量子图灵机的概念，具体如下：犽条带量子图灵机是一个五元组犕（

34、犙，狇，犙狉，犽，），每个犻是带有空白符号犫的有限字符集，犙是包含初始状态狇和终止状态犙狉狇狉，狇狉，，狇犽狉的内部状态有限集合，是从犙犽到犆犙犽的多值量子转移函数令犽犽即：犙犽犆犙犽是由犣索引单元格的双向无限纸带，读写头沿着纸带向左，向右或者不移动，分别用，表示它的模拟能力有如下的结果在文献中介绍了良构引理和完全引理作为刻画特征的依据设犕是犽带良构的如果输入狓后犕在时间犜

35、（狓）内停机，那么存在犽带良构的犕输入（狓，犜（狓）在时间犜（狓）内停机由文献中命题说明在二次多项式时间内可以通过一个单带模拟，记作狆这与经典情况类似，与具有多项式等价的计算能力到此我们介绍了几种量子图灵机模型及其变形综上所述，它们在计算能力上是有联系和区别的具体地说，广义量子图灵机（）的计算能力涵盖了量子图灵机（）量子图灵机（）的计算能力

36、涵盖了随机预言量子图灵机（）在二次多项式时间内可以通过一个单带的模拟在图中形象化地描述了它们之间的关系图量子图灵机模型之间的关系量子图灵机类似于经典计算下的概率图灵机，但是与经典图灵机（包括概率图灵机）并不相同一方面，量子图灵机可以看做是由量子读写头和一条无限长的带作为量子存储器组成的“带”上的每个单元格均表示一个量子记

37、数位，可以以“”和“”的叠加态形式存在，这样可以在带上同时对编码问题的许多输入进行计算，计算结果是所有输入对应结果的叠加，通过测量得到经典结果另一方面，它们之间的区别是状态转移函数的变化量子图灵机含有复量子状态转移函数，进行犜步计算只需要精度为犗（犜）位的转移幅度就足够了由于量子图灵机的运算结果不再按概率叠加，而是按概率振幅叠加，量子相

38、干性在量子图灵机中起着本质性作用这是实现量子并行计算的关键，这个性质也是量子图灵机和概率图灵机的重要差异证明了可以有效地模拟经典的可逆图灵机，这意味着量子计算至少与经典计算有相同的计算能力将这个结果形式化量子计算复杂性概论一个问题的量子计算复杂性是由求解这个问题的量子算法的计算复杂性所决定量子计算复杂性是指在量

39、子环境下对于某个问题求解的困难程度，包含问题复杂性、算法复杂性等由于求解一个问题的量子算法可能有多个，它们的量子计算复杂性也各不相同因此在理论上定义一个问题的量子计算复杂性为求解该问题的最有效量子算法的计算复杂性目前，研究的问题主要有两种：一是可行性检验问题，二是判定问题在经典的计算复杂性理论中，人们已经证明存在多项式时间

40、通用图灵机求解可计算问题类似地，和指出存在多项式时间通用量子图灵机求解可计算问题同时，他们提出了量子计算复杂性理论随后，许多学者提出了各种量子算法和量子复杂性证明作为量子计算复杂性的进一步解释譬如，定理说明量子计算优于经典计算，即存在具有有界错误概率的量子谕示图灵机求解问题的复杂性低于经典计算的复杂性算法和算法分别验

41、证了定理的正确性但是对于任意（或趋近）无穷多的输入，量子图灵机（包含任意的概率图灵机）以有界错误概率求解问题需要（亚）指数时间复杂度一方面，量子图灵机的出现降低了求解问题的计算复杂性；另一方面，不是所有的问题都在内量子问题复杂性分类由于量子计算机可以看做是经典计算机在量子环境下的推广于是，问题的经典复杂性、、、等可类似地推广到量子

42、计算中，即有、、、等期张焕国等：量子计算复杂性理论综述量子模拟类问题我们给出称之为问题的重要语言，具体定义如下：犔：存在一个多项式时间犕使得犔犔犕，其中犔犕狓：犕接受狓若存在多项式时间犕，它在编码策略犲之下能够求解问题，则判定问题，即犔，犲它被看作类问题在量子环境下的模拟另外，类问题是指以精确或者无错误的量子多项式时间接收的语言类，即相应地，它

43、的时间复杂性（犜（狀））是指由输入长度为狀，运行时间为犜（狀）精确界定的接收的语言类类问题是指以至少的概率在多项式时间内接收的语言类，即类问题是指在多项式时间内以的概率接收的语言类它的时间复杂性（犜（狀））是指输入长度为狀，运行时间为犜（狀）界定的以概率接收的语言类它的计算能力有结果量子模拟类问题问题在量子环境下有两种不同的模拟定义：一

44、种类似于用定义问题的定义方式，即是指由多项式时间的识别的语言类；另一种是多项式时间验证语言类的扩展，即在经典计算理论中，这两种问题类的定义方式是等价的然而，在量子计算理论中这两个定义并不等价，文献给出和两者满足的关系：：犣（，（，犮，）如果存在一个多项式时间的量子验证者犞，对于任意的输入狓，满足（）狓犃，存在犽（狓）量子证明使得犞至少以犮（狓）的概率

45、接受狓，（）狓犃，对任意给定的犽（狓）量子证明，使得犞至多以狊（狓）的概率接受狓问题犃（犃，犃）的复杂性记作（犽，犮，狊）在等人的文章中说明了对于任意的多项式限制函数犽，任意犮使得（犽，犮，）（，犮，）的定义如下：设问题犃（犃，犃），狆是一个多项式限制函数，函数犪，犫：犖，那么犃狆（犪，犫）当且仅当存在一个多项式时间的线路族犙犙狀：狀犖，其中每一个犙狀有狀狆（狀）个比特的输入和一个比特的输出

46、，满足下面的性质：（）完整性对于所有的狓犃，存在狆（狓）个量子比特态使得犙接受（狓，）犪（狓）；（）可靠性对任意的狓犃和狆（狓）量子比特态使得犙接受（狓，）犫（狓）问题定义如下：识别的语言犔，当且仅当存在和一个多项式函数犘使得狓犔（犕在狆（狓）步内接受狓）在文献中指出它的计算能力有如下的结果，，犽，犙犽犆另外在量子环境下可以模拟经典的问题在文献中介绍了一个特殊的语言分

47、类，即定义如下犕，狓，狋犕编码一个量子机器在狋步内以非零概率接受狓文中指出难于确定准确的概率接受问题而确定准确的概率接受问题是一个问题这说明的复杂性不低于求解问题的复杂性，有除此之外，在文献中给出了另一个量子模拟问题的定义，即问题，简记为在文献中证明了量子环境下的团问题是问题在文献中讨论了问题的另一个量子模拟问题它不同于问题像这样

48、的完全问题还有许多其他的形式，在文献中讨论了更多的完全问题的情况，譬如，，（），，但目前的研究不是很充分，在这里我们不做过多地叙述其他类问题在文献中给出了的量子模拟的定义，并指出犽犽且在文献中介绍了和类问题是使用函数代替接受概率产生的语言类在文献中给出了它们的计算能力分类，即，在文献中证明了且于是结合前面的结论有另外，在

49、文献中得到结果，其中的介绍参见文献文献介绍了类问题是指具有后选择能力的量子计算机在多项式时间内解决的问题，且证明了文献考虑了量子模拟困难问题的计算能力之间的关系，得到如下的结果，其中是一类特殊的（后来的文献如文献把它也称作）同时还得到了结果在文献中作者研究了计算机学报年，，，，，，计算能力的量子解释，给出了如下结果

50、其他的结果参见文献文献认为到目前为止大部分的量子算法问题可以规约到量子采样现有的许多问题，譬如离散对数问题、图表同构等都属于问题在文献中指出了这些问题在量子环境下有如下结果在文献中作者讨论了类问题与的关系，指出，文献介绍了类问题它是指存在多项式时间的量子线路族犙犙狀：狀犖，其中每一个线路犙狀有狀量子比特的输入和一个量子比特的输出

51、，满足下面的性质：（）对于所有的狓犃，使得犙接受（狓，）；（）对任意的狓犃，使得犙接受（狓，）它的计算能力有结果文献解释了类问题具体的定义如下，设犿是多项式有界函数，犪，犫：犖，是多项式时间可计算函数语言犔（犪，犫，犿）当且仅当存在犿个量子消息验证者犞，满足下面性质：（）完整性对所有的狓犔，存在量子验证者犘使得犞以至少犪（狓）的概率接受狓；（）可靠性对所有的狓犔，对每个量子验证者犘

52、使得犞以至多犫（狓）的概率接受狓对每个有界多项式函数犿，（）（犿，）并且定义犿（犿）关于类问题的计算能力有如下一些结果文献证明了，比文献中的结果更精确在文献中指出（）在文献中证明了（，，犪，犫），（犪，犫）于是，在图中刻画了量子模拟的、问题与经典复杂性之间的关系更详细的复杂性讨论结果总结在图中图经典复杂性与量子复杂性之间的关系图文中讨论的量

53、子与经典复杂类总结关系量子线路复杂性在电子环境下，布尔电路可用于描述经典图灵机在量子计算出现以后，首次提出量子线路模型于是布尔电路被推广到量子计算中，量子图灵机也可以采用量子线路进行描述随后，指出量子图灵机模型和量子线路模型是等价的在某种情况下，它们多项式时间可以互相模拟，这开启了一个新的量子信息技术研究领域，量子线路复

54、杂性理论量子线路是将布尔线路模型中的比特和逻辑门推广到量子线路模型中量子线路是多量子位的酉变换，将初始状态集合映射到某个终止状态通常的酉门可以分解为一个或者两个量子位的基础门线路图代表了一系列酉演化和测量，包含输入状态和输出测量线路图每次从左到右运行每个水平线代表量子信息向前传播一次每条线代表一个量子位的量子信息酉门由

55、线上的盒子表示，门的符号写在盒子里量子线路模型是一个很好的量子计算模型它为量子算法的构造和量子计算机的物理实现提供了一个框架由于量子图灵机的操作是可逆操作，量子图灵机的逆操作变换处理相当于把每一个量子逻辑门用一个需要更多量子比特输入的量子逻辑门代期张焕国等：量子计算复杂性理论综述替这意味着当量子图灵机对应的量子线路

56、进行逆操作时，所付出的代价只是额外增加了按照线性增长的量子比特数目量子线路模型通过组合一组基本的量子逻辑门，实现具有特定功能的线路该模型可以清晰、直观地模拟量子信息处理的过程，对我们设计量子计算装置和新的量子算法都有很好的指导作用这样的文章有很多，譬如文献量子计算复杂性理论中最重要的两个模型是量子图灵机模型和量子线路模

57、型在量子计算中，计算过程是复杂的，尤其是表示数据的量子态的转换和控制变量处于基状态的过程是十分重要的量子线路模型不用考虑这些方面，它更侧重于考虑输入的量子态在幺正运算的操作下得到的结果它类似于均匀多项式线路，是可逆线路的推广使用该模型能够更方便地描述量子算法量子线路模型的主要优点是模型简单，描述问题比较直观，并且有利于理

58、解和设计量子算法在量子系统中，量子线路模型提供了非常方便的物理演化形式，如量子超密编码、量子隐形传态以及算法等量子算法复杂性理论量子算法的时间复杂性设犜犕（狓）表示量子图灵机犕对输入狓计算得到一个最终格局所用时间，或者称时间复杂性；否则无定义若犜犕（狓）存在，且犜犕（狓）犜，则犕对输入狓的计算在时间犜停机对所有输入狓均停机的犕，其时间复杂性函数犜犕：犣犣：犜犕（

59、狀）狋：狓，狓狀，使得犕对输入狓的计算需要的时间为狋若存在一个多项式犵（狀），使得对所有的狀犖，有犜犕（狀）犵（狀）即若存在多项式犵（狀），对每个输入狓，犕在时间犵（犳（））内精确停止，则犕称为多项式时间若函数犵（狀）是指数形式的，那么犕称为指数时间图多项式时间量子算法与指数时间量子算法复杂度比较图对多项式时间量子算法与指数时间量子算法的复杂度进行比较分析，其中犔是多

60、项式时间量子算法复杂度，另外两个是指数时间量子算法的复杂度关于多项式时间量子算法与指数时间量子算法，给出以下几点注记：（）定义的量子时间复杂性是在最坏情形下的度量求解某一问题的一个量子算法，对于该问题的绝大多数例子是有效的但是可能对问题的某个极端例子表现极差从而导致这一量子算法是指数时间量子算法（）关于问题的难解性一个量子

61、算法本质上并不依赖于特定的编码策略和具体的计算模型这是因为这些定义划分在多项式变换下可相互规约而不同的合理编码策略给出同一问题的描述，相应的输入长度（或长度的上界、下界）之间最多相差一个多项式倍数，且从一种编码容易转换到另一种编码类似地，多项式时间界定的量子计算模型在单一时间单位内所完成的工作量，相对于多项式的复杂性函数是

62、等价的一般不具体提及特定的编码策略和量子计算模型，只简单地称某一算法是多项式时间量子算法或别的类型的量子算法问题等众所周知，经典算法复杂性是基于经典图灵机进行讨论的类似地，量子算法复杂性是基于量子图灵机进行分类的由前面所述，量子图灵机的定义有许多，最常使用的是随机预言量子图灵机现有许多已知的量子算法都属于这个模型，譬如算法

63、、搜索算法、算法等谕示“ ”可以作为一个黑盒，使用者不必考虑它的细节在考虑某个算法的量子复杂性时，必须考虑如何去构造这个谕示，且构造谕示需要多少资源（包括量子比特和量子逻辑门）如果可以用构造谕示得到有效的解，则称这个问题在量子环境下是可解的但是并不是所有的量子算法都需要使用谕示有些量子算法就不使用谕示模型，譬如文献，，目前我们

64、只考虑带有谕示的量子图灵机模型它的计算能力有如下的两个重要的结果定理设犙（犃）是运行时间受限于犜（狀）犗（狀）的随机谕示量子图灵机从犙（犃）中随机唯一地选取谕示犃的概率为，则基于犙（犃）的问题中不包含问题，即定理设犙（犅）是运行时间受限于犜（狀）犗（狀）的随机置换谕示量子图灵机从犙（犅）中随机唯一地选取置换谕示犅的概率为，则基于犙（犅）的问题中不包含问题，即计算机学

65、报年为了更直观地理解量子算法的优越性，在表我们总结了一些困难问题的经典算法复杂性和量子算法复杂性表一些困难问题的经典算法复杂性和量子算法复杂性待解决问题经典算法复杂度量子算法复杂度黑箱问题犗（狀）犗（）因子分解（犮（狀）（狀）犗（（狀）（狀）（狀））问题下上界分别是（狀狀），（狀狀）犗（狀）求阶问题（狀狀槡狀）犗（）求解线性方程组槡狀犽犗（狀）最短向量问

66、题（）犗（狀）狀狅（狀）结构和随机置换的区分犗（狀）犗（狀）搜索问题犗（犖）犗（犖）矩阵乘法验证犗（狀）犗（狀（，槡狀）子集合问题犗（狀狀）犗（狀狀）碰撞问题犗（狀槡狉）犗（狀槡狉）从表中，我们可以看到，某些困难问题的经典算法的复杂性超过量子算法的计算复杂性某些类问题的量子算法可以多项式地规约为类问题基于这些问题所构造的密码在量子环境下，将不再安全而某些类问题的量子算法

67、不能多项式地规约为类问题，则基于这些问题困难性构造的密码体系仍然不能被量子计算攻破另外，由于，使得在电子环境下不安全的密码在量子环境下一定是不安全的量子环境下的数据复杂性在文献中我们着重讨论了数据复杂性计算复杂性理论描述了计算对资源的消耗，如时间和空间资源目前的计算复杂性理论主要研究时间复杂性和空间复杂性除了时间和

68、空间外，数据也是一种重要的计算资源在计算过程中，如果需要的数据量过大而实际上无法获得，那么计算也将不能完成数据复杂性的概念最早用于电子计算环境下对密码的差分攻击对于轮以下的由于需要的选择明文数量较少，在机上几分钟就可以攻破但对于标准的轮密码却不能攻破，因为需要个选择明文，这在实际上是很难得到的这里影响差分攻击是否成功的重要

69、因素是其数据复杂性与经典的情况类似，这里提出的量子环境下的数据复杂度包括输入数据复杂度和处理数据复杂度两方面输入数据复杂度是指完成某个量子算法所需输入的数据量处理数据复杂度是指运行该量子算法所要处理的数据量通常，我们采用其主要部分来描述计算复杂度譬如，在搜索算法中需要将搜索算符执行狀次这说明搜索算法的处理数据复杂度是很大

70、的另外，在算法中设待分解的合数是狀位的，则它的输入数据复杂度是犗（狀）又因为它的处理数据复杂性不大故算法可以有效计算大合数的因子分解问题于是在标准量子谕示的意义下，我们给出量子计算情况下的数据复杂性的定义，且给出了基于数据复杂性分类的容易和困难问题定义定义令是一个狀量子比特的量子图灵机的数据复杂性是一个函数犳：犖犖，其中犳（狀）是在运

71、行时输入和处理的所有数据量之和令狀狀狀，则犳（狀）犳（狀）犳（狀），其中狀、狀分别是储存输入数据的储存器和运算处理数据的储存器的量子比特数，犳（狀）、犳（狀）分别表示输入数据量和处理数据量定义令是一个狀狀狀量子比特的量子图灵机，其中狀，狀分别是储存输入数据的储存器和运算处理数据的储存器的量子比特数假设量子图灵机的数据输入能力和处理数据能力分别是犵（狀）和犵（

72、狀）量子图灵机在时间犜犚内运行解决某类问题的量子算法时，需要的数据总量为犳（狀）犳（狀）犳（狀），其中输入数据量是犳（狀），处理数据量是犳（狀）（）若存在正整数狀使得对所有的狀狀狀狀满足狀（犳（狀）犵（狀）犳（狀）犵（狀））犽，犽是正常数，则称该问题在量子图灵机环境下是容易计算的；（）若狀（犳（狀）犵（狀）犳（狀）犵（狀）），则称该问题在量子图灵机环境下是计算困难的在经典计算中，布尔函

73、数是一种重要的函数狀期张焕国等：量子计算复杂性理论综述，，，元布尔函数一共含有狀种情况设犆狋（犳）是计算布尔函数犳的规模最小的布尔线路犆，且犆中每个逻辑门的输入不大于狋如果狋，则用犆（犳）犆（犳）表示文献中指出几乎所有的狀元布尔函数犳均满足犆（犳）（狀狀）这说明只有少数的布尔函数存在有效的经典算法类似地，我们将这一结果推广至量子计算中布尔运算包括逻辑非、逻

74、辑和与逻辑积在布尔线路中，所有的逻辑非门变换到最底层，作为一个输入变量因此，布尔线路中仅含有逻辑和和逻辑积运算通过适当地增加用于储存逻辑运算结果和表示逻辑非的量子比特数，量子线路能够成功地模拟布尔线路不同的是，在布尔线路中每个逻辑门（逻辑和和逻辑积）的输入是两个经典比特，而量子线路图中每个量子逻辑门的输入是四个量子比特不失一般

75、性，在量子计算中我们把这些逻辑运算视作由一组量子逻辑门构成的黑盒众所周知，量子门按照输入的量子比特数可以分成单比特、二比特及多比特量子门这些量子比特门构成一个集合组在这里我们忽略具体的量子逻辑门，只根据输入的量子比特数划分于是，量子线路中出现的量子逻辑门的数量称为量子线路的尺寸如果两个线路有相同的输入和输出，则称它们是等价

76、的如果不存在含有更少量子比特门的等价量子线路，则称该量子线路的尺寸是最小的设犖（狀，犛）表示计算不同布尔函数的量子线路的数量，其中狀表示量子比特数，犛表示量子线路中的量子逻辑门数引理对任意的犛有犖（狀，犛）犛（狀）犛由引理直接得到下面的结果定理设量子计算机有狀个量子比特在标准谕示模型下，不存在多项式尺寸的量子线路计算所有的布尔函数在文献中我们

77、得到了与经典情况相似的结论，即不存在多项式规模的量子线路计算布尔函数虽然到目前为止，我们仍未能找到具体的布尔函数的布尔线路或量子线路的规模是超线性函数的但这表明即使在量子计算中，仍有许多的计算是量子计算不能有效完成的于是我们得到重要的结论，即输入数据复杂性很大的问题是抗量子计算的换句话说，若某个计算任务的输入数据量与计

78、算所有的布尔函数的数据量是一个数量级的，则该问题是抗量子计算的不论是电子环境还是量子环境下，时间复杂性、空间复杂性和数据复杂性都是重要的复杂性分类它们彼此之间是互相关联和影响的在算法运行过程中需要空间储存数据，这就涉及到空间复杂性有时算法运行需要的数据太大可能会超过储存能力另一方面算法运行时需要处理数据越多，则处理时间就

79、越长此外，在量子计算中态之间的转换是复杂的譬如，经典态到量子态（或量子态到经典态）转换的过程是复杂的，而量子态之间的转换是容易实现的这对量子计算机的影响是很大的在量子计算内部的数据处理是量子态的，而显示给人看到的数据是经典态的所以在输入输出数据的环节，量子计算机的速度和量子计算机的处理速度相比是慢的在密码设计上，我们可以利用这

80、个特点如果我们设计的密码使得攻击该密码需要极大的输入输出数据复杂性，则该密码就可以抵御量子计算的攻击量子基本运算和犛犺狅狉算法的优化实现量子计算的通用模型包括，一种是基于一系列门和测量来实现的，另一种仅包含量子测量目前大部分的量子计算研究重点是第一种下面通过实现量子计算机中两个量子比特狓和狓的与操作方案，解释一下量子计算

81、的过程（）采用个量子比特位的变换来表示狓，狓，狔；（）置第个量子比特为，即狔；（）对狓，狓，执行犝操作，定义犝：狓，狓，狓，狓，狓狓，其中狓狓表示狓和狓的经典与操作结果，而表示模加；（）对第个量子比特进行（，）测量，测量结果作为犝操作的结果通过对以上的运算策略进一步推广，已经证明量子计算机能够完成经典计算的任何任务而加法作为经典计算的基础运算，在量子计算中能成功地被

82、模拟在文献中给出了包括加法、模加、模乘、模幂基本运算的量子线路图利用模幂运算可以实现量子算法它使用一个线性增长的辅助储存器执行分解大因子算法图个两位数的量子加法在文献中作者优化了原始的量子加法基本运算的量子线路图在此基础上，我们进一步优化了量子加法基本运算的量子线路图以量子比特为例（见图），对比文献给出的位输入，位计算机学报年输

83、出和位输入，位输出的量子加法，我们的方案使用的量子比特数均比原方案少一个，且量子门更加简单通过对比出现的量子加法路线图的构造，得到结论：量子加法的构造可用受控非门和门连接而成做简单的推广粗糙地得到一个结果，对犿（犿）个数据的加法可以用一个犿个数的一位加法和多个犿个数的一位加法元件组合而成，表达式为犝（犿，狀）犝狀（犿，）犝（犿，）设符号犛犻犼表示

84、对第犻位和第犼位的元素进行加法运算设犜狀表示含有狀个量子比特参与运算的门设犝（犿，狀）表示犿个狀位量子比特数的加法例犝（，）犝（）犝（，）犝（，）犛犛犛犛犆犜犆犜犛犛犛犛犆犜这个例子不一定是最佳方案，得到的扩展方案与同类方案比较，使用的量子比特数和量子门更少算法是重要的量子算法之一算法的出现使得量子算法求解整数分解问题优于任何已知的经典算法这个标准的量

85、子算法刺激了量子信息处理的研究与量子计算机的实际实现在过去的年中，利用优化技术，算法的在各种不同的平台上进行了实现证明了量子求解整数问题的有效性但是，在实验方面算法的执行需要很高的条件，一个充分大的量子寄存器和高保真的量子控制因此，这对于量子算法的优化和实验的简化都是一个重要的挑战量子算法的优化和实验的简化是可能的一般地

86、，理论上的优化结果好于实验的结果在算法优化方面出现了很多的成果利用狀个量子比特构造了一个量子线路，其中狀是待分解数的比特长度该量子线路使用了犗（狀狀）量子逻辑门该线路比的量子线路方案更优不仅量子比特数减少一个，而且量子逻辑门少一半通过利用量子傅里叶变换构建更复杂的算术乘法器（累加器），量子常数和常数的量子分频器来实现算法它们

87、可以有效地执行量子模乘运算这个量子线路需要狀个量子比特付向群等基于半经典量子傅里叶变换的方法，设计了一个新的量子线路该线路需要犗（（狀）量子逻辑门，需要的量子比特数比初始方案多个量子比特，但是实现速度增加倍随后，付向群等将这个结果进行了推广由于大维数量子寄存器生成的困难性，基于小维数量子寄存器实现大维数量子变换的方法，与等人的实

88、现线路相比，计算资源大体相同，所需量子寄存器的维数前者较后者多狋维，而实现速度提高了狋倍，狋是窗口宽度算法的实验方面也有许多的成果在处理量子编码技术中，普遍使用的是量子光学电路等在硅芯片上利用单光子量子比特实现了分解的算法实现了光子集成控制非（）栅偏振编码的量子比特，对于逻辑真值表的量子门表现出其高的保真度这表明这个门的能力

89、将可分离状态转换成纠缠的利用该技术可以实现算法虽然算法在理论上是一个成熟的算法，但是在实现上存在着距离由于量子算法是一个概率算法，并不能保证算法每次都能成功通过优化可以提高算法的成功率，接近到目前为止，对算法实现方法的优化都是基于算法实现所需的量子比特数，基本量子门数量和实现速度方面去研究算法的优化在硬件实现方面，尽管已

90、经出现了一些实现的方案，但是实现的位数较少，仅处于实验室阶段目前，对量子计算研究者而言还不能使用真正的量子计算机，更多地是使用经典计算机模拟量子算法进行验证实现量子计算的经典模拟对量子计算理论和量子算法正确性、可行性的研究具有重要意义可以通过经典模拟进行超前研究，但是经典计算机的计算速度和存储空间远不能满足量子计算机的需

91、求，它的验证范围也有限这限制了经典模拟的发展如何构造更好的经典模拟环境，并有效地和目前计算机系统结合也是一个重要的研究内容目前使用的量子模拟器有、、、等模拟器主要是对目前比较成熟的量子算法的模拟，比如、以及小波变换等其他量子计算模型除了上面讨论的以外，其他量子计算模型还有量子计数模型、量子查询模型、量子黑箱模型、量子通信模型

92、等而单向量子模型和绝热量子模型的出现为量子计算研究带来了新思路而量子衍生算法，量子遗传算法等丰富了量子算法的应用领域单向量子模型用于量子水印技术等，绝热量子模型更多地用于分解大合数问题对偶量子模型可以允许在量子算法的设计中使用非酉算符各种量子模型的出现对研究量子算法求解问题是有利的，丰富了研究的领域期张焕国等：量子计算

93、复杂性理论综述，，：：，格密码的量子安全性格理论及其困难问题格理论的研究开始于世纪它被作为一个算法工具用来解决数学和计算机科学中的一系列问题，这包括密码分析和公钥密码设计等格被看做是一种具有周期性结构的狀维点空间集合格密码有很多优势首先，它具有抗量子计算的潜力其次，格算法具有简单易实现、高效性、可并行性特点它的运算简单，通常

94、只涉及矩阵、向量之间的线性运算第三，格密码已经被证明在最坏条件下和平均条件下具有同等的安全性因此格密码可以作为抗量子密码领域的一个候选方案下面介绍格中的一些困难问题定义（格的定义）给定狀个线性无关的向量犫，，犫狀犚狀，由它们生成的向量集合犔（犫，，犫狀）狀犻狓犻犫犻，狓犻犣称为格向量犫，，犫狀称为格犔的一组基任意一组基可以用一个实数矩阵犅犫，，犫狀犚狀狀表示，矩

95、阵的列向量由基向量组成使用矩阵表示后，一个格可以用矩阵的语言描述为犔（犅）犅狓，狓犣狀，其中犅狓表示一个矩阵与向量的乘法定义（狇元格）给定正整数狇，犿，狀，矩阵犃犣狀犿狇，可以得到下面两个狇元格：狇（犃）狔犣犿，狊犣狀，狔犃狊（狇），狇（犃）狔犣犿，犃狔（狇）第个狇元格由犃的行向量生成，第个格包含了所有与犃的行向量模狇正交的向量在格理论中有许多的困难问题首先介绍最短向量问题（）及其

96、变型问题其次，介绍另一个重要的格问题类，最近向量问题（）及其变型问题定义（最短向量问题（））对于一个犱维格犔犣狀给定一组基犅，找到一个非零的向量狌犔满足狌狏犔狏格中的最短向量是不唯一的因为如果狌是最短向量，狌也是其中符号表示范数年在欧几里德范数中提出了范数的限定概念直到年和将其推广到任意范数年建立了二次型与丢番图近似之间的联系，其中一个中心问

97、题就是证明格中最短向量的存在年证明了在犾范数下是难的年证明了在犾狆（狆）范数下的困难性对大多数应用来说，最短向量定义在犾范数上大多数情况下，不要求最短只要近似最短满足计算要求即可定义（近似最短向量）给定近似因子和一组基，找到一个非零向量狌犔，使得狌（犔）求解问题最著名的算法是算法，对近似因子狅（狀），算法是个多项式时间算法求解近似目前，对

98、近似因子狀（是一个任意小的常量）的在准多项式归约下是难的定义（最短向量）给定犱维格犔犣狀的一组基犅和一个近似因子，找一个非零向量狏使得其范数满足狏（狏狅犾（犔））犱如果格的体积是易计算的，则确认正确的解也变得容易了常量确保犱时至少有一解，而（犔）槡犱狏狅犾（犔）犱因为算法可以找到一组基，使得第一个向量犫（犱）狏狅犾（犔）犱，其中因此算法可以解决近似因子为（犱

99、）的问题定义（最短长度问题）给定犱维格犔犣狀的一组基犅和一个近似因子，找到一个值（犔）满足（犔）（犔）（犔）当时，（犔）（犔）定义（唯一最短向量）对于一个满秩格犔犣狀的基犅和一个间隙因子，找到最短非零向量狏犔，其中狏是惟一的（对其他任何向量狓犔满足狓狏，且至多是向量狏长度的倍的向量都平行于狏）定义（最短基问题）给定一个犱维格犔犣狀的基犅和一个近似因子，找到一组基犅犫，，犫犱满足犻

100、犱犫犻犻犱犫犻，计算机学报年：：，，：其中犅犫，，犫犱犅（犔）是犔的任意一组基当时，犻犱犫犻犻犱犫犻定义（最短向量决策问题）给定犱维格犔犣狀的一组基犅，一实数因子狉和一个近似因子，决定（犔（犅））狉或（犔（犅））狉即如果（犔（犅））狉，结果直接返回如果（犔（犅））狉，结果直接返回否则，如果狉（犔（犅））狉，那么和都可被返回这个问题被称为问题对任何常量近似因子，是难的定义（最短独立向量问

101、题）给定犱维格犔犣狀的一组基犅和一个近似因子，找到一组犱个线性无关向量狌，，狌犱满足犱犻狌犻犱（犔）此外，另外一个重要的格问题类是最近向量问题（）及其变型问题定义（最近向量问题）给定犱维格犔犣狀的一组基犅和一个目标向量狓狊狆犪狀（犔），找到一个向量狌犔，满足狓狌犱犻狊狋（狓，犔）定义（近似最近向量问题）给定犱维格犔犣狀的一组基犅，一个目标向量狓犚和一个近似因子，找到一个向量

102、狌犔，满足狓狌犱犻狊狋（狓，犔）第一次提出比困难一些（对同一维数来说）后由扩展开来，提出一个预言，对各种范数解决就可以解决（在相同维数下）定义（有界距离译码）给定犱维格犔犣狀的一组基犅，一个距离参数和一个目标向量狓狊狆犪狀（犔），找到一个向量狌犔满足狓狌犱犻狊狋（狊，犔）（犔）当目标向量距格不远于（犔）时，和是一样的定义（最小整数解）给定一个模狇，一个矩阵犃犣狀犿狇（犿狀）和一

103、个实数常值狏，找到一个非零向量狌犣犿，满足犃狌（狇），且狌狏狏的选择保证了解的存在这是因为狓狇犲犻是犃犡（狇）的平凡解，所以狏的选择通常小于狇年和指出在一个随机格狇（犃）中解问题至少和求解平均状况的一样困难，其中狏的选择满足的条件定义（非齐次最小整数解）给定狇（犃）的一组基，找到一个向量狏犣狀狇满足犃狏（狇）如果存在一个算法可以找到解且狏（对给定的范数界），则

104、称算法成功将上式右边的替换为狔，则得到问题的一个非齐次状态，记为（狇，犿，）如果不存在有效的算法在多项式时间狋内，以不小于的概率求解（），则（）是（狋，）难的问题的定义为犚狀，犿，狇，（（犃，狔），狓）犣狀犿狇犣狀狇犣犿，狓，犃狓狔狇等得到了问题的一个变型版本，使得犚狀，犿，狇，（（犃，狔），狓）犣狀犿狇犣狀狇，犿，狑狋（狓），犃狓狔狇文中指出对给定犿和狆犾狅狀（狀），任意的素数狇狀（狀槡），近

105、似因子犗（槡狀），求解平均情况下的狇，狀，犿，和狇，狀，犿，问题，同最差条件下近似和问题的困难性相同除了最短向量问题（）、最近向量问题（）之外，还有一类被称为带误差的学习问题（）它在密码学中有着广泛的应用下面简单介绍一下带误差的学习问题（）及其变型问题定义（带误差的学习问题）选取参数狇作为大整数模，狊犣狀狇是一个狀维向量，是犣狇上的一个概率分布，犃狊，是犣狀狇

106、犣狀狇的一个概率分布，分布样本选取如下：（）从犣狀狇中随机均匀选取犪；（）通过在犣狇上选取犲；（）返回元组（犪，犪，狊犲）给定狀，模狇，犣狇上的一个概率分布和分布犃狊，中的任意多个相互独立的样本，找到狊定义（带均匀误差的问题（犝））给定正整数犿，狀，狇狇（狀），输入对（犃，犫），其中犃犣犿狀狇，向量犫犣犿狇，误差犲犣犿狇服从均匀分布犣犿狇，找到向量狊犣狀狇满足等式犫犃狊犲格问题的难解性在年将傅里叶变换应

107、用到格困难问题及格密码的分析上，考虑了最坏情况下的唯一最短向量问题（）解的情况，并提高了和的格密码的安全性指标，同时在文章中给出了存在量子算法求解狀犮问题的充分条件在年等人考虑了一个特期张焕国等：量子计算复杂性理论综述殊的最短向量问题槡狀，证明了该问题属于，即问题在量子环境下的模拟在年等人考虑了其他的格困难问题，近似最短向

108、量问题（）和近似最近向量问题（），证明了这两个问题属于，故在标准量子谕示模型中不存在有效的量子算法求解这两个格困难问题随后，在年首次考虑了利用量子算法求解特殊的格困难问题文中证明，在陪集抽样实验中如果存在算法求解二面体群的隐藏子群问题，那么存在算法求解唯一最短向量问题（）另外，文中讨论了二面体群陪集问题，指出如果存在带有

109、失效参数犳的算法求解二面体群陪集问题，那么存在量子算法求解狀（）犳唯一最短向量问题结合这两点，作者给出了（狀）唯一最短向量问题到平均情况下的子集和问题的量子规约但是提出的量子算法的时间复杂性是犗（犖（犖槡））年修改了原来的量子算法，将量子空间复杂性降低到多项式规模，而时间复杂性仍是亚指数的年等人在改进的量子算法基础上讨论了最短

110、向量问题（），提出新的量子算法的复杂度是犗（狀犗（狀）这一结果优于、、等人的经典算法复杂性同年，等人在文献中利用局部敏感的哈希函数（）加速格基筛选，将求解最短向量问题（）的时间和空间复杂度分别降低到犗（狀犗（狀）和犗（狀犗（狀）等人在文献中提出新的启发式算法求解最短向量问题（）在不增加新的寄存器的情况下，该算法的时间复杂性和空间复杂性分别

111、是犗（狀犗（狀）和犗（狀犗（狀）在年提出了问题，并讨论了它的难解性，给出从问题到问题的量子规约，其中问题是问题的一个变型在量子规约下，问题与最坏情况下近似因子为犗（狀）的问题一样困难，其中是与扰动分布方差相关的实际参数年等人在环上考虑了问题，假设不存在多项式的量子计算机求解最坏情况下的理想格问题，那么环的分布是随机的基于格的密码学这些格困难

112、问题的出现为设计新的格密码方案提供了理论上的支持公钥密码年和提出第一个格密码方案，简称为该公钥密码体制是基于犗（狀）的最坏情况困难性在年等在文中针对密码体制的解密失败问题给出消除解密错误方案，并且给出了一种新的密码体制将安全性提高到犗（狀），但新方案并没有基于格的困难问题，这就失去了与之等价的安全性年提出了一个新的困难性

113、相当于犗（狀）的公钥密码体制密码体制是定义在欧氏向量空间集合上该安全参数狀是向量空间的维数令犿狀且狉狀狀狀引入符号犅狀表示狀维立方体，犅狀狓犚狀：狓犻狉狀，犻，且对于犮，将半径为狀犮的狀维球记作犛狀狓犚狀：狓狀犮私钥是从狀维单位球中随机选择的向量狌在犅狀上定义的广义函数犎狀有如下的结构：（）从狓犅狀：狓，狌犣中随机均一地选取元素狓（）从集合犛狀中随机均一地选取误差向量狔，，狔狀（）输出

114、狏狓狀犻狔犻同时从犎狀中随机选取狀犿个向量狑，，狑狀，狏，，狏犿作为公开密钥其中狑犻满足从狑犻到由狑犼生成的超平面（犻犼）的最小距离不小于狉狀狀加密过程：加密是逐比特进行的首先加密比特，令犫，，犫狀从，中随机选取并且归约向量狀犻犫犻狏犻模平行六面体犘（狑，，狑狀）狀犻犻犻：犻将狀维向量作为密文其次加密比特从平行六面体犘（狑，，狑狀）中随机选取狀维向量作为密文解密过程：对于密文犮，通过密钥狌可以计

115、算出明文如果犱犻狊狋（犮，狌，犣）狀，那么密文解密为比特；反之解密为比特密码体制存在以下个方面的问题：（）解密失误由于密码存在解密失误的现象，所以必须保证解密错误以比较低的概率发生，否则大量解密错误会使无法使用减少扰动参数可以有效降低解密错误发生的概率，但扰动参数计算机学报年太小，就可能泄露私钥信息因此密码是一种（）效率问题由于是由逐比

116、特加密的，比特的信息被加密成为实空间中的一个点数据扩展和内存需求很大但是由于已经被证明平均安全性与最坏安全性相同因此如果加密的明文不多，又要求具有较高的安全性，那么就可以考虑使用方案（）实用性问题为了使方案能够抵抗概率算法攻击，必须满足狀如果狀，那么公钥大小为字节，并且每比特的明文加密后将变成一个比特的密文如此大的公钥和加密数

117、据扩充，使在普通的公钥密码应用中难以接受因此实用性大大受到限制公钥密码在年、和设计了简称为的密码体制，并给出了一个基于问题的单项陷门函数，使用这种函数可以用来做为公钥加密后的数字签名这也是第一次基于格的签名它对加密体制进行了改进避免了解密失败的现象该体制有两个参数，分别是格维数狀和安全参数它们是由最近向量问题加密的困难性决

118、定的私钥是由矩阵犚给出矩阵犚的列构成格犔的一组基这些基构成合理的短整向量设计者在文中给出了集中构造犚的方法公钥由公开的矩阵犅构成，它的列表示犔的不同的基与犚不同的是，犅不能归约到犚设计者给出了两种方法能随机地从犚中生成犅随后提出更有效的厄米范式作为公开基（见本文第页脚注）加密过程：为了加密一个信息，将它进行编码为整向量犿犣狀令误差向量犲随机地取自集

119、合，狀，计算密文犮犅犿犲解密过程：对于密文犮，解密得到明文犿犅狀犚犚狀犮，其中符号：犚犣运算规则是四舍五入对于狓（狓，，狓狀）犚狀，计算狓（狓，，狓狀）犣狀分析过程：在密码体制里，每个明文犿对应格点犿犔犅犿在加密过程中，明文犿首先转换成对应的格点犿犔，然后通过增加误差向量犲计算得到密文犮因此，通过选择和犲使得犿犔是最接近密文犮的格向量为了得到明文犿犔（或者犿），那就必须解决最短向量问题因此

120、解密过程是由的关于近似问题四舍五入方法构成的在年针对近似问题提出两种方法，分别是四舍五入方法和最近平面算法按照的方法，当使用密钥犚时效率很好，当使用公钥犅解密时工作效率很差，即解密时按照的方法使用密钥可以得到正确的格向量犚犚犮因为犚犿犔是整向量，由的方法知道犚犚犮犚犚（犿犔犲）犚（犚犿犔犚犲）犿犔犚犚犲如果犚犲犫是非零向量，那么犚犫是非零的格

121、向量此时，按照的方法不能得到正确的格点，即恢复出错误的消息因而，当犚犲时加密是正确的同时，误差向量具有（，，）形式增加值意味着增加格向量犿犔和密文犮的距离，使得问题更难于求解且解密错误的可能性增加另一方面按照方法利用公钥犅解密将会失败这是因为公钥犅不能归约到密钥犚上这意味着利用格基归约解决问题等价于解决近似最短向量问题为了保证安全性，其公钥

122、尺寸至少需要，私钥尺寸也必须大于这使得密码体制的使用价值也不大公钥密码在年、和提出了简称为的密码体制，同传统的公钥方法相比，它具有较小的密钥长度、较快的加密和解密时间等优势除此之外，在安全性方面也有优势，即存在潜在的抗量子计算能力这是因为到目前还没有有效的量子算法解决密码体制的基础格问题在最近的十几年来，关于密码体制的安全

123、性问题的研究已经变得十分活跃在国际上，密码体制已经作为标准这也是到目前为止最好的基于格问题的公钥方案密码体制包含加密和签名，这里只是介绍加密在介绍密码加密体系之前，先引入两个多项式函数的定义，选取整数犖，设多项式函数犳犪犖狓犖犪狓犪和多项式函数犵犫犖狓犖犫狓犫的次数小于犖定义犺犳犵犮狀狓狀犮狓犮，其中犮犻犻犽犪犼犫犽这个和是对所有满足犼犽犻（犖）的（）加

124、密过程通过预处理阶段，将明文犿表示成次数小于犖且系数的绝对值至多为（狆）的多项式，并选择一个小的多项式计算密文犮狆犺犿（狇）期张焕国等：量子计算复杂性理论综述（）解密过程计算犪犳犮狆犵犳犿（狇），其中多项式犪的所有系数的绝对值至多为狇所以明文犉狇犪狆犉狆犵犉狆犳犿犿犿（狆）密码体制的说明：因为在密码体制中次数是犖的多项式犳和犵定义的运算犳犵需要犖个乘法，所以在加解密

125、一个长为犖的明文时，需要运算犗（犖）次的运算，因而密钥的长度为犗（犖）当密码体制的参数狀变为狀时，加密过程中的两个狀次多项式变为两个狀次的，加密狀狆比特的计算量从狀变为狀个，即密码体制的加密速度与狀成反比（）解密失败在解密过程中，若犪狆犵犳犿（狇）不等于狆犵犳犿，而是存在一个非零多项式狌使得犪狆犵犳犿狇狌于是犉狆犪（狇）犿狇狌犉狆（狇），其中（狆，狇）当狆不能整除狌时狇狔犉狆（狇），解密

126、失败在的技术报告上将解密失败分为越界错误和越距错误越界错误是指多项式犵犳犿的系数超出狇，狇），但是最大的系数和最小的系数之差不超过狇；如果最大的系数和最小的系数之差超过狇，称为越距错误同时越界错误可以用中心化方法纠正（）密码体制的攻击到目前为止已经有各种各样的攻击方法针对密码体制，下面介绍一些已有的攻击方法：设犺犺犖狓狀犺构造一个犖犖

127、矩阵犎犺犺犺犖犺犖犺犺犖犺犺犺烄烆烌烎用行向量分别表示多项式犳犪犖狓犖犪狓犪和多项式犵犫犖狓犖犫狓犫，记为犳（犪，，犪犖）和犵（犫，，犫犖），那么犳犎犵（狇）设犐为犖犖单位矩阵，构造一个犖犖矩阵犕犐犎狇（）犐设犔由矩阵犕的行向量生成的格由于犵犳犵（狇），所以存在多项式狔有犵犳犵狇狔将狔表示成一个犖维的行向量狔，那么（犳，狔）犕（犳，犵），其中（犳，狔）是犖维行向量故有（犳，犵）在格犔中，由于犳和犵均有小的系数，使得（犳，犵）在格犔中是一个

128、短的向量于是将密码体制建立在寻找最短向量问题（问题）穷举攻击攻击者试图试遍所有的密钥犳，使得犳犵（狇）有小的值；或者试遍所有的多项式犵所以攻击者如果想恢复明文，需要试遍可能的多项式计算得到明文犿犮犺（狇）而多项式犵的规模小于多项式犳的规模，所以密钥的安全由多项式犵的规模决定同时明文的安全由多项式的规模决定其次是中途相遇攻击作者指出存在分别

129、针对多项式和密钥犳的攻击随后在文献中继续了这一工作简单地说，将密钥犳分成两半犳犳犳，分别计算狓犳犺和狓犳犺因为（犳犳）犺犵（狇）和犵是二进制的，所以狓和狓模狇后只是与的不同假设犳有偶数犱犳个，犳有犱犳个，那么从犖次多项式中任取一个向量狓，其系数满足狇（狓）犻狇对于狓的每一个系数定义一个比特犻，其中若系数狓则犻反之犻进而定义一个犖比特的字符串犪：：犖设表示比特的余，犪表示犖比特的字符串的

130、补所以犳被分为两个储存盒，分别储存犪和犪因为狓狓犵，使得犪对应狓犳犺和犪对应狓犳犺当犳犳犳时，使得犪犪即存在多项式犳，犳在盒内检测出碰撞对于这些碰撞能从储存的盒中恢复出多项式犳，犳同时在文中估计了这种攻击的复杂性槡犖犖犱犳（）犱犳犱犳烄烆烌烎第种是多种传输攻击如果数次发送同一个明文犿，但是使用同一个密钥和不同的随机多项式进行加密，攻击者可能恢复大部分的明文现在发送密文犮犻狆

131、犻犺犿（狇）其中犻，，狉攻击者计算（犮犻犮）犺（狇），从而得到狆犻狆（狇）因为多项式犻非常小，以至能恢复出确定的狆犻狆，从而得到多项式的一些系数如果狉比较小，那么可以通过穷举搜索恢复出明文因此建议在加密过程中增加干扰，使得能抵御这种攻击方式第种格攻击已知的攻击主要是针对公钥犺和明文犿与利用公钥攻击一样，攻击者是利用类似的方法找到，使得相对容易找到目标

132、向量（犿，）对于利用格基归约方法的攻击，就需要使格具有足够高的维数，使得格基归约算法失效但是这样的结果使得加解密算法变得很慢，效率降低已知当最短向量与犖维格的犖次根判别式相比很小计算机学报年时，格基归约算法有很高的成功概率利用这种方法，利用公钥犺攻击，如果攻击者能选择合适的实数，将矩阵犕中的犐替换为犐使得目标向量（犳，犵）相对更容易找到，这样就

133、可以提高攻击的效率文献中给出了参数选择的方法或者在格犔中另找一个向量（狊，狋）满足犺狋狊（狇），使它尽量短，那么解密时，有犮狋狆狊犿狋（狇）若狆狊犿狋的系数没有越界，即狆狊犿狋（狇）与狆狊犿狋相等，计算（狆狊犿狋）狋犿（狇），即可得到明文但是还不能证明格中的困难问题的计算复杂性低于普通的格而对其他参数进行限制，也可以降低攻击的效率譬如，在加密过程中如果狆犺犿（狇）等于狆犺

134、犿，即多项式狆犺犿系数的绝对值至多为狇攻击者在截获密文后直接计算狆犺犿（狆），可得到犿犿（狆，犿）如果狆与犿互素，可以直接恢复出明文；如果狆与犿不互素，犿是犿的整数倍，通过选择参数可以恢复出明文所以这要求狆犺犿（狇）不能等于狆犺犿在年和发表论文提出一种选择密文攻击选择密文犲犮犺犮，其中犮是整数，犺是公钥攻击者将密文发给，经解密有犪犳犮犺犮犳（狇）犮犵犮犳（狇），其中多项式犳

135、和犵的系数等于，或，因而多项式犮犵犮犳的系数为，犮，犮选择适当的犮值满足犮狇犮假设多项式犮犵犮犳的所有项中只有狓犻项的系数为犮，则犮犵犮犳（狇）犳犮犵狇狓犻将结果狇狓犻犉狆（狆）返给攻击者因为（狆，狇），于是得到狓犻犉狆的逆元狓狀犻犳所以能得到一组与（犳，犵）等价的密钥（狓狀犻犳，狓狀犻犵）当多项式有多个系数为犮，此事只要改变密文的形式，经过一系列的计算最终得到等价密钥（狓狀犻犳，狓狀犻犵）同时

136、在文中作者列举出了在一些参数下的攻击成功的概率在年等人针对密码体制提出了恢复密钥攻击具体算法描述如下：（）初始化密钥犳犖犻犳犻狓犻，输入密文犮犖犻犮犻狓犻和整数有犳，犳犼，其中犼犖；犮犼，其中犼犖；（）犻，，犖有如下过程：如果狇，那么令犮犻犳犻，反之犮犻；如果狇，那么令犮犻狇，反之犮犻；解密密文犮；在解密过程中如果犪犳犮，令犳犻，并且忽略到；令犮犻犮犻；解密密文犮；在解密过程

137、中如果犪犳犮，令犳犻，并且忽略；令犳犻；（）令犳犻犳犖犻，其中犻，，犖；（）返回犳犖犻犳犻狓犻该算法得到密钥犳的错误率最多是犖狇，但是该算法在加密时需要使用犗（犖）次，过程变的十分复杂在年和等人在文中提出两种选择明文攻击密码体制这两种攻击一开始都要求寻找能破译密文的或可以构成解密失败的对（犿，）第种攻击要求固定多项式和选择不同的明文犿现在逐个将明文犿的非零系数

138、变为如果使得变化后的明文犿能解密成功，保持这个系数不变，反之令该系数为将这一过程继续直到明文犿能够导致解密失败此时多项式狊狆犵犿犳的系数至少有一个超出了狇，狇）的范围，而它的系数为狊狆犖犻犻犵犼犻犖犻犻犳犼犻，其中犻，犵犻，犳犻表示多项式，犵，犳的第犻项系数譬如当狆时，犿犻的值是，，而犳犼犻的值按照如下的方式定义：若犿犻且将犿犻变为解密成功，则犳犼犻；若犿犻且将犿犻变为解密成功，则犳犼

139、犻；若犿犻且将犿犻变为解密成功，则犳犼犻；若犿犻且将犿犻变为解密成功，则犳犼犻，反之犳犼犻然后寻找新的解密失败的明文和来确定其他的系数具体的分析细节可以参见文献第种攻击要求固定明文犿和选择不同的多项式与第种方法相似，选择解密失败的对（犿，），计算（犵）犖犻犻犵犖犻，其中（犵）表示多项式犵的常数项系数当犻犵犖时，称和犵有正碰撞；当犻犵犖犻时，称和犵有负碰期张焕国等：量子计算复杂性

140、理论综述撞于是和犵的净值碰撞等于正碰撞减去负碰撞，即（犵）等价于净值碰撞因为大部分随机选取的与犵有正的净值碰撞，通过分析中的和能够恢复犵的非零系数在实践中当犻时有种情况：高频率犵犖犻；随机频率犵犖犻；低频率犵犖犻同样实践中对犻时有种情况因此攻击者可以分析犻得到犵的系数的值，进而得到密钥犳具体的分析细节可以参见文献密码体制的扩展：在年和提出关于密码体制的非

141、填充的扩展方案，可以消除解密失败与传统的密码体制不同，选择公钥犎犉狇狉（狇）和犔狆犉狇狉（狇），其中狉狆和一个随机多项式狉加密过程：选择随机多项式狉，计算密文犮犿犎犔狉（狇）解密过程：收到密文以后，计算犪犮犳犿狉狆狉狉（狇）通过选择狆和狇使得犪的系数小于狇，即恢复出明文犿犪（狇）参数的设置：同传统的密码体制一样，明文的系数在狆和狆之间为了不降低安全性，使得多项式狉和狉不可逆，且格

142、的维数大于于是多项式犿狉最多有狆犖项，多项式狉狉最多有犖项为保证解密的正确性使得多项式犪的系数在狆和狆之间，必须满足狆犖狆犖狇，即狇狆犖随后作者在文中对前面提到的攻击传统的密码体制的方法进行分析，通过分析指出可以抵御这些攻击比较而言，选择密文攻击是已知的效果比较好的攻击方法为了保护密码的安全性，在年和针对选择密文攻击先后提出了种填充方案

143、因为对于密码体制中没有有效的安全性证明，所以这种填充方案对密码体制的弥补并不能从本质上得到解决，只是对漏洞进行弥补提高了安全性，以及需要很小的计算开销，具体的安全性说明可参见和的文献虽然有普遍的填充方案，但是相比较和密码体制而言，密码体制的散列成本相对于加解密不能忽略不计下面介绍这个填充方案：设哈希函数犎：，犿，狀设明文犕是犽比

144、特长的字符串在加密过程中需要随机犽比特长的字符串犚，其中犽在到之间且犽犽犿令符号表示字符串的连接填充方案：在加密过程中，使用随机字符串犚得到密文犮犇（犕犚；犎（犕犚））填充方案：令哈希函数犉：，犽?，犽且表示按位异或，于是可以得到密文犮犇（（犉（犚）犕）犚；犎（犕犚））填充方案：首先将明文犕和随机字符串犚分成相等大小的块，犕珨犕犕和犚珚犚犚令哈希函数犉和犌是集合，犽犽到集合，犽犽的映射，计算

145、犿（犕犚）犉（犕犚）和犿（犕犚）犌（犿），于是得到密文犮犇（犿犿；犎（犕犚））关于密码体制的变种方案有很多譬如，在年和提出简称为的密码体制，希望借助大的密码空间达到较好的安全性；在年和提出简称为的密码体制，其加密效率更高且密钥长度增加；同年，等人针对解密错误提出一种补偿算法；在年胡予璞教授对该方案进行了改进，具体的内容可以参看相关的参考文献：年在矩阵环

146、中证明了关于密码的一个结论，指出如果在非交换系统设计中设计相应的变种密码，那么它在加密和解密计算过程中能抵御格的攻击；在年文献针对公钥密码体制是容易受到多个传输攻击这个不足，通过研究指出线性化攻击技术能恢复出明文公钥密码年，在发表的文章中提出了一个简称为密码体制，对于安全参数狀，设犖狀和犿犮犿狀，其中犮犿是特定的常数令（狀）（狀槡狀）

147、或者当狀趋于无穷时满足（狀）槡狀趋于无穷一方面，选择一个较小的函数（狀）产生强的安全保障另一方面，这也使得解密更容易出错可以选择函数（狀槡狀）是最小的（狀）函数使得解密出错的概率可以忽略不计具体的文中建议选择（狀）狀狀设犎犺槡犖，槡犖）犳狉犮（犺）犿，其中犳狉犮（狓）狓狓，狓犚，且对狓，狔犚，犳狉犮（狓），犳狉犮（狓）狓和犳狉犮（狓狔）犳狉犮（狓）犳狉犮（狔）随机选取犺犎作为密钥计算机学报

148、年，：：，令狓犖，狔犚，分布函数犜狓，狔（狉）犽槡狔狔（狉狓犽）（），另一分布函数犙狔（狉）犽槡狔狔（狉犽）（）下面我们增加一个归一化因子将分布函数犜狓，狔扩展到非整数令实数犺和狉，，），重新定义犜犺，（狉）犙（狓犺）狓犙（狉犺）根据上面提到的分布函数，随机选取值狓，，犺和值狔犙如果狓狔犺，令狕狓狔犺反之，继续重复这一过程于是，选取（狀），（狀）并按照上面的过程选择狓，，狓犿和狔，，狔犿使得狕，，狕犿犜犺对

149、犻，，犿，设犪犻犖狕犻和犻是整数且使得狓犻是奇数（这样的犻概率存在的指数接近）将（犪，，犪犿，犻）作为公钥加密过程：随机选取集合，，犿的一个子集犛逐比特加密明文，加密比特时计算犻犛犪犻模犖；加密比特时计算犻犛犪犻犪犻模犖解密过程：令犱犖犺，如果犳狉犮（）犱，那么解密为反之为，其中，，犖密码体制的公钥长度为犗（犖），逐比特加密的密文长度为犗（犖）逐比特加密方案使加密速度过慢而且密文扩展比

150、较大，使得工程实现不方便随后年和分别对该密码体制进行改进，使公钥长度和密文扩展为犗（犖），但是改进的算法安全性不再直接建立在格困难问题上公钥密码在年和提出了一种简称为密码体制它建立在近似格问题上的密码体制，从单位球犛狀狓狓随机选取向量狌和犿个字母的随机置换作为密钥由于允许指数小的舍入误差，不妨假设向量狌的坐标是有理数，其分母是限制在

151、非常大的整数的范围内设犿犮狀，不妨令犮设犎犻狏：狏狌犻表示垂直于狌的超平面公钥是参数犫和集合狏（），，狏（犿），其中犻犣，狏犻犎犻满足狏犼狌犖犼犣选择数列犖犼使得犖犫和犖犻犻犼犖犻犫，犻，，犿加密过程：加密犿位的明文犘（，，犿），其中犻或者，那么将犘加上一个扰动进行计算得到密文犿犻犻狏（犻），其中向量狉是随机选取的且满足狉犫解密过程：通过使用密钥狌计算下面的内积犛狌犿犻（犻狏（犻）狉）犿犻（犻）犖犻狌狉下面使

152、用贪心算法能高效地从犛中恢复出（犻），并且使用秘密的得到（犻）如果（犿），那么犛犖犿犫；若（犿），那么犛犖犖犖犿犫因为犖犿犿犻犖犻犫犻，用犛犛（犿）犖犿代替原来的犛，重复这一过程直到得到（犻）使用秘密的置换，得到明文，，犿在密码体制中的犿犗（犖）位明文是加密的密文狀维向量，而不是仅仅一个比特的明文在年月，刊登了中国国家数学与交叉科学中心潘彦斌和邓映蒲关于格密码体制的论

153、文，其审稿意见认为该密码体制已被完全攻破潘彦斌和邓映蒲给出了它的一个唯密文攻击，时间复杂性是多项式的，从而彻底攻破了该存在有十多年的密码体制展望目前，虽然出现了一些量子算法，但是量子计算的理论研究还很不充分现有的量子算法应用于解决经典可计算问题，而对于不可计算问题在量子环境下却没有进行充分讨论，如停机问题考虑了量子可计算性的

154、概念，并且借助量子连续变量和量子绝热演化，提出了一个解决第问题（停机问题的一个等价问题）的量子算法和在数学意义上构造了一个解决有无穷多堆硬币情况下的零售商问题（停机问题的一个等价问题）的量子设备如果算法在物理上能够实现，则量子计算为解决经典的不可计算问题提供了新的方期张焕国等：量子计算复杂性理论综述法这将对计算科学和密码

155、学产生巨大的影响和指出算法感兴趣的是可计算性问题而不是计算复杂性但是，认为，他所构造的通用量子图灵机模型并不能计算非递归函数，即他构造的模型在计算能力上不与论题矛盾而以后提出的直接或间接地建立在提出的量子图灵机模型的基础上这说明，从现有的的角度不可能突破论题考虑新的，可能对这个问题有帮助等人从另外的角度告诉我们，对量子

156、可计算理论的研究，似乎应该从数学，物理学甚至更多不同学科的角度去研究目前广泛使用的公钥密码、、等分别依赖于大整数质因子分解，离散对数问题，椭圆曲线上的离散对数问题然而在量子计算机上求解这些问题存在多项式时间量子算法量子计算机的发展，将对这些公钥密码体制构成严重的威胁量子计算复杂性理论有助于我们构造一些抗量子密码，进而确保

157、量子计算环境下的密码安全尽管量子计算复杂性理论在理论方面取得了一定的研究成果，但是，人们对量子计算的复杂性以及量子计算机实现的研究还处于初级阶段，还有许多问题有待更深入的研究关于量子计算求解问题有一个有趣的观点，量子计算可以被看作格局叠加态上的许多线性算子若量子计算机采用非线性时间演化，则能够在多项式时间求解问题文献采

158、用非线性量子逻辑门，给出了求解问题的一个量子算法文中证明，若量子计算机能够用非线性算子设计格局叠加态上的算子，则能够在多项式时间求解问题这也是一个十分重要的问题，如果这个问题能够得到正面的解决将对密码学产生致命的影响现在被认为是抗量子计算的密码都将受到挑战另外，在图理论和组合理论中某些著名的问题存在量子算法这些量子算法

159、至少相对于经典算法是加速的量子计算机是否能在多项式时间内求解所有的类问题呢？在量子算法方面，自因子分解和搜索算法提出后，虽然各国众多的研究者在该领域进行了大量的研究但目前，还没有发现其他解决经典问题的新量子算法在量子问题复杂性关系，及其与古典问题复杂性关系方面，还有许多不确定包含关系如与、的关系？三个复杂类、和中有两个是

160、相同的吗？等等由于量子算法的出现，使得在经典计算下的类问题在量子环境下仍是容易求解的，即一些在经典计算下是困难的问题，譬如大整数分解和离散对数问题等，在量子计算下是容易求解的而另外一些类问题即使在量子计算下仍然是困难的在第节我们介绍了问题在量子环境下的模拟定义分为两类，和但它们并不是最困难的问题分类，从关系图中看到在它们之

161、上还有，（）等问题分类如果我们把量子模拟的和问题作为困难问题对待，就像类问题在经典计算中的作用一样，那么我们可以看到类问题即使在量子环境下也是困难的在年证明了带有常数的字方程式可满足性问题是困难的，而也被称作的这样的问题还有其他的定义这对设计抗量子计算的密码而言是一个好消息从而设计者可以在经典环境下选择更困难的问题设

162、计抗量子计算的密码关系图有利于对困难问题的理解和密码的设计这是基于对问题复杂性做出的分析另一方面，从算法复杂性的角度考虑根据我们提出的数据复杂性定义，如果某个计算任务需要处理的数据量规模等价于计算布尔函数的数据量犗（狀），那么该计算任务是不能完成的，即使是在量子计算环境下这也为设计抗量子计算的密码提供了一种新的思路当今互联

163、网信息化时代，各个国家都十分重视密码学的理论和技术研究目前流行的公钥体制主要包括基于大整数分解问题的和基于椭圆曲线上离散对数问题的公钥体制，即这些体制有一个共同的弱点，即不能抵抗量子攻击因此，一旦实用的量子计算机出现，这些体制将可能被攻破，从而被淘汰而且随着计算机技术的飞速发展，这些体制也逐渐遭受一些新的威胁因此，寻找新的公

164、钥体制，特别是能抵抗量子攻击的公钥体制，便成为一件重要而迫切的工作量子计算复杂性理论的发展为设计实际应用的公钥密码奠定基础此外，设计能够走向实际应用的抗量子计算的公钥密码也是密码学的一个关键技术而格密码被认为是后量子时代最主要的公钥体制代表之一，它以能抵抗量子攻击、平均安全性可以建立在格问题最坏情况复杂性及快速的加解密

165、速度等优点受到了广泛的关注现有的研究表明，还没有出现有效的量子算法计算机学报年解决格上的困难问题目前最好的结果都需要指数级的资源消耗，并且能够走向实际应用的公钥密码不多这都需要进一步的研究参考文献，：，，（）：，，：，，（）：，，（）：，，，：，，，，（）：，，（）：，，，，，，（）：，，，，，（）：，，，（）：，，，（）：

166、，，：，：（）（张焕国，管海明，王后珍抗量子密码体制的研究现状中国密码学发展报告长沙：电子工业出版社，：），，，：，，：，，，：，，，，，（）：，，，，，（）：，，（）：，，，，，（）：，，，（）：，，，：，，，，：，，（）：，，，：，，（）：，，：，：，，：，，，，，，（）：，，，，（）：，，，，，：，，，：，，（）：

167、，，，，，，：，：期张焕国等：量子计算复杂性理论综述，，，，，（）：，，，（）：，：，：，，，，（）：，，，：，：，，，，，（）：，，（）：，，，（）：，，，：，：，：，，，（）：，，，，，（）：，，，（）：，，，（）：，，，（）：，，：，，，，（）：，，（）：：，，：，，：，，，，（）：，，，（）：，，，，（）：

168、，，，：，，（）：，，（）：，，，，，（）：，，，，，，：，，，，：，，：，，，（）：，，，，（）：，，（）：，，，，（）：，，，，：计算机学报年，，，，（）：，，，，，，，：，，， “ ” ，，：：，：，，，，，（）：，，，：，，，：，，（）：，，：，，，，（）：，，，，，：，：，，，：，：，，，，（）：，，，，

169、（）：，，，，，（）：，，，，，（）：，，，，，（）：，，，，，（）：（）（王冬，陈汉武，朱皖宁等多值逻辑量子置换门的酉矩阵表示计算机学报，，（）：），，，，，（）：，，（）：，，，（）：，，，（）：，，，：，，（）：，，，，（）：，，：，：：，：，，：，：，，，，，（）：期张焕国等：量子计算复杂性理论综述，，：，，，，（

170、）：，，：，，，（）：，，，，：，：，：，，，，，（）：，，，（）：（）（吴昆，马雷量子全加器构造的探讨量子电子学报，，（）：），狀，，（）：狀，，（）：，，，（）：，，，，（）：，，，狋，，（）：（）（付向群，鲍皖苏，周淳等比特半经典量子变换科学通报，，（）：），，，，（）：，，，，，（）：，，，，，（）：，，，，，（）

171、：，，，，（）：（）（张毅，卢凯，高颖慧量子算法与量子衍生算法计算机学报，，（）：），，，（）：（）（王宇平，李英华求解的量子遗传算法计算机学报，，（）：），，，，（）：，，，，，（）：，，，，，（）：，：，，（）：，，，，，（）：，，：，：，：，：，，：，：：，：，，（）：，，：（）计算机学报年：，：，，（）：，（），，：，

172、，，（）：，，（）：，，，，（）：，，，：，，，（）：，，，，，，：，，：，：，（），：，，，，（）：，，，：，，：，，：，：，，，，，：，，，，：，：，，，（）：，，：，：，，：，：，：，，：，：，，，，：，，，，，（）：犗（狀狀），，：，，，（）：，，，，，（）：，，（）：：，，（）：，，，（）：，，，（）：，，，，（）：，，：期张焕国等：量子计算复杂性理论综述犣犎犃犖犌犎狌犪狀犌狌狅，，，，，犕犃犗犛犺犪狅犠狌，，，犠犝犠犪狀犙犻狀犵，，犠犝犛犺狌狅犕犲犻，，犔犐犝犑犻狀犎狌犻，，，犠犃犖犌犎狅狌犣犺犲狀，，，犑犐犃犑犻犪狀犠犲犻，，，犅犪犮犽犵狉狅狌狀犱（，），（），（）（），，，，，计算机学报年

展开阅读全文