量子搜索算法研究

发布时间：2017-04-05 17:00

  本文关键词：量子搜索算法研究，由笔耕文化传播整理发布。

【摘要】： Grover量子搜索算法是量子计算机上的一个穷举算法,该算法以(?)量级的加速及其广泛的应用受到人们的关注(N=2~n为数据库的大小),本文对量子搜索算法进行了深入的研究,在提高算法成功率和降低特定条件下算法计算复杂性方面取得了以下结果: 1.基于相位变换的量子搜索算法研究。将Grover量子搜索算法的π相位变换用任意Φ=φ(0≤Φ,φ≤2π)相位变换所替换,分析了算法成功率与任意相位变换、迭代次数及目标元素个数之间的关系;给出了给定迭代次数下的最优相位和算法成功率的最小值,进而以算法成功率和迭代次数二者间的权衡来选择不同的相位变换设计新的量子搜索算法;提出了1.018相位变换和0.062相位变换的量子搜索算法,算法的迭代次数分别为(?)和(?),对任意目标元素个数M,算法成功率不低于93.43%和99.96%。 2.量子部分搜索算法研究。对量子部分搜索算法中的最一般情况——多目标元素任意分布在多个目标块中进行了分析;刻画了含有不同目标元素个数的目标块进行Grover迭代时块中各元素几率幅的变化关系;给出并证明了多目标元素任意分布在多个目标块的量子部分搜索算法成立的条件,该条件保证了量子部分搜索算法能够以成功率为1和最小的迭代次数完成搜索;通过具体的数值运算,得出了目标元素个数分布情形与量子部分搜索算法所需的迭代次数之间的关系。 3.量子中间相遇搜索算法研究。针对密钥可分型密码,将中间相遇攻击的思想引入Grover量子搜索算法,给出了量子中间相遇搜索算法,该算法利用空间换时间,以一定的存储复杂性为代价,大大降低了密钥穷尽的计算复杂性;在此基础上提出了三个密钥的三重DES量子中间相遇搜索算法,该算法的计算复杂性为O(56×2~(56)),存储复杂性为O(2~(56))。
【关键词】：量子搜索算法 部分搜索算法 相位变换 多目标元素 中间相遇
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：O413;TN918.82
【目录】：

• 摘要6-7
• Abstract7-8
• 第一章 引言8-11
• 第二章 基础知识11-14
• 2.1 量子比特11
• 2.2 线性算子与矩阵11-12
• 2.3 量子并行性12
• 2.4 量子测量12-14
• 第三章 量子搜索算法14-24
• 3.1 未加整理的数据库搜索问题14-15
• 3.2 oracle15-16
• 3.3 算法过程16-18
• 3.4 算法几何可视化18-19
• 3.5 算法迭代次数19-21
• 3.6 算法最优性21
• 3.7 算法成功率21-24
• 第四章 基于相位变换的量子搜索算法研究24-42
• 4.1 多解情况下量子搜索算法的改进方法24-25
• 4.2 相位变换与Grover量子搜索算法25-28
• 4.2.1 π相位变换的Grover量子搜索25-26
• 4.2.2 任意相位变换的Grover量子搜索26-27
• 4.2.3 任意相位变换的相位匹配条件27-28
• 4.3 一次任意相位变换的量子搜索28-36
• 4.3.1 一次任意相位变换28-33
• 4.3.2 多目标元素的量子搜索算法一33-35
• 4.3.3 多目标元素的量子搜索算法二35-36
• 4.4 k次任意相位变换的量子搜索36-41
• 4.4.1 k次任意相位变换36-39
• 4.4.2 1.018相位的量子搜索算法39-41
• 4.5 小结41-42
• 第五章 量子部分搜索算法42-55
• 5.1 GRK部分搜索算法42-47
• 5.1.1 部分搜索问题43
• 5.1.2 相关定义43
• 5.1.3 算法描述43-44
• 5.1.4 算法分析44-47
• 5.2 多目标元素平均分布在多目标块中的部分搜索算法47-50
• 5.2.1 算法描述47
• 5.2.2 算法分析47-50
• 5.3 多目标元素任意分布在多目标块中的部分搜索算法50-54
• 5.3.1 算法描述50
• 5.3.2 算法分析50-53
• 5.3.3 数值计算53-54
• 5.4 小结54-55
• 第六章 量子中间相遇攻击55-62
• 6.1 经典中间相遇攻击55-56
• 6.1.1 级联密码模型描述55
• 6.1.2 对级联级密码模型的中间相遇攻击算法描述55-56
• 6.1.3 算法分析56
• 6.2 量子中间相遇搜索算法56-58
• 6.2.1 算法描述56-57
• 6.2.2 算法分析57-58
• 6.3 三重DES的量子中间相遇搜索算法58-61
• 6.3.1 三重DES介绍58-59
• 6.3.2 对三个密钥的三重DES量子中间相遇攻击59-60
• 6.3.3 算法分析60-61
• 6.4 小结61-62
• 结束语62-63
• 参考文献63-66
• 作者简历 攻读硕士学位期间完成的主要工作66-67
• 致谢67

【相似文献】

中国博士学位论文全文数据库 前2条

1 李盼池;量子计算及其在智能优化与控制中的应用[D];哈尔滨工业大学;2009年

2 宋辉;量子计算机体系结构及模拟技术的研究与实现[D];中国人民解放军国防科学技术大学;2003年

中国硕士学位论文全文数据库 前5条

1 钟普查;量子搜索算法研究[D];解放军信息工程大学;2009年

2 李筠;量子随机行走搜索算法研究[D];华东师范大学;2006年

3 陈彦辉;量子算法模拟与设计[D];吉林大学;2005年

4 苏昶;量子计算技术及其在信息安全中的应用研究[D];河北工业大学;2007年

5 钟艳花;量子算法研究及其核磁共振实验的仿真实现[D];广东工业大学;2004年

  本文关键词：量子搜索算法研究，，由笔耕文化传播整理发布。

本文编号：287332