高概率量子随机行走搜索算法研究

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

  本文关键词：高概率量子随机行走搜索算法研究，由笔耕文化传播整理发布。

【摘要】：量子信息技术的迅猛发展对现代密码体制产生了巨大冲击,量子搜索算法以其强大的计算能力成为量子计算中的重要研究方向。但量子计算算法在实现过程中产生的误差不可避免,从而影响量子计算算法的有效性,并且搜索空间也可能会含有多个目标解。因此,研究误差对量子搜索算法的影响和多目标解条件下的量子搜索算法有重要的理论意义和实际应用价值。量子随机行走是近年来量子计算算法中研究的热点问题之一,其主要原因是：基于量子随机行走构造的搜索算法,不仅能解决无序的数据库搜索问题,还能解决Grover算法不能有效解决的问题(如空间搜索,元素区分),因此,基于量子随机行走的搜索算法引起了广泛关注。2003年,Shenvi, Kempe和Whaley共同提出了一个基于超立方体上量子随机行走的搜索算法,简称SKW算法。2008年,Potocek又在SKW算法的基础上提出了高概率SKW算法。本文主要对高概率SKW算法进行了深入研究,主要研究成果如下：1.基于Grover扩散算子的高概率SKW算法系统相位误差的研究。通过对高概率SKW算法几何描述,建立了含有相位误差的算法模型；对给定规模的数据库,刻画了算法成功率、迭代次数和相位误差之间的关系；对给定大小的相位误差,给出了算法所能达到的最大成功率、所需迭代次数以及对误差的容忍度；分析和数值模拟表明,对相同大小的相位误差,高概率SKW算法的成功率比Grover算法的成功率变化更小,表明高概率SKW算法对误差的鲁棒性更强。2.高概率SKW算法中的退相干研究。超立方体上链接会随机断裂,从而在高概率SKW算法运行时产生退相干,通过引入包含断裂链接的转移算子,提出了含有退相干的高概率SKW算法；通过数值模拟和采样分析,对给定的退相干率,给出了算法所能达到的最大成功率和所需迭代次数；针对退相干会减少算法迭代次数但也会降低算法最大成功率,给出算法存在退相干时的概率复杂度(迭代次数/概率),并得到退相干率的两个临界值,当退相干率在它们之间变化时,刻画了退相干率与概率复杂度之间的关系。3.多目标解条件下的高概率SKW算法研究。通过数学归纳法,给出了多解条件下量子随机行走通用搜索算法的计算复杂度求解方法,解决了量子随机行走通用搜索算法的多解搜索问题；通过证明多解条件下SKW算法就是超立方体上的量子随机行走通用搜索算法,给出了多目标解条件下高概率SKW算法的计算复杂度；通过数值模拟和分析,得到关于目标解占搜索空间比例的一个临界值,当目标解的比例不大于这个临界值,刻画了高概率SKW算法的成功率与迭代次数、解的比例之间的关系。
【关键词】：量子搜索算法 量子随机行走 相位误差 鲁棒性 退相干 多目标解 通用搜索算法
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O413;TP391.3
【目录】：

• 摘要4-5
• Abstract5-9
• 第一章 引言9-13
• 第二章 基础知识13-23
• 2.1 量子计算基本概念13-15
• 2.1.1 量子比特13
• 2.1.2 线性算子13-14
• 2.1.3 张量积14
• 2.1.4 量子并行性14-15
• 2.2 随机行走15-20
• 2.2.1 经典随机行走15-17
• 2.2.2 量子随机行走17-20
• 2.3 超立方体上量子随机行走搜索算法20-22
• 2.3.1 SKW算法20-21
• 2.3.2 高概率SKW算法21-22
• 2.4 本章小结22-23
• 第三章 高概率量子随机行走搜索算法中的系统相位误差研究23-37
• 3.1 高概率SKW算法的几何描述23-27
• 3.2 含有相位误差的算法模型27-30
• 3.2.1 模型建立27-29
• 3.2.2 算法分析29-30
• 3.3 数值模拟30-35
• 3.4 本章小结35-37
• 第四章 高概率量子随机行走搜索算法中的退相干研究37-47
• 4.1 随机链接断裂退相干37-39
• 4.2 产生退相干的高概率SKW算法39-41
• 4.2.1 算法描述39
• 4.2.2 算法特性39-41
• 4.3 数值模拟及分析41-46
• 4.4 本章小结46-47
• 第五章 多目标解条件下高概率量子随机行走搜索算法47-61
• 5.1 量子随机行走通用搜索算法47-49
• 5.2 多解条件下量子随机行走通用搜索算法49-52
• 5.3 多解条件下高概率SKW算法分析52-55
• 5.4 数值模拟55-58
• 5.5 本章小结58-61
• 第六章 总结与展望61-62
• 致谢62-63
• 参考文献63-67
• 作者简历67

【参考文献】

中国期刊全文数据库 前6条

1 Fada Li;Wansu Bao;Xiangqun Fu;;A quantum algorithm for the dihedral hidden subgroup problem based on lattice basis reduction algorithm[J];Chinese Science Bulletin;2014年21期

2 LIU Yang;;Deleting a marked state in quantum database in a duality computing mode[J];Chinese Science Bulletin;2013年24期

3 ;t-bit semiclassical quantum Fourier transform[J];Chinese Science Bulletin;2012年01期

4 ;A quantum algorithm for searching a target solution of fixed weight[J];Chinese Science Bulletin;2011年06期

5 ;An N/4 fixed-point duality quantum search algorithm[J];Science China(Physics,Mechanics & Astronomy);2010年09期

6 ;Quantum mechanical meet-in-the-middle search algorithm for Triple-DES[J];Chinese Science Bulletin;2010年03期

  本文关键词：高概率量子随机行走搜索算法研究，由笔耕文化传播整理发布。

，

本文编号：304024