离散量子行走研究

发布时间：2020-10-16 10:54

　　 二十一世纪是一个快速发展的信息时代,电子计算机在社会发展中起到了至关重要的作用。当前电子计算机发展已经进入到一个瓶颈期：高度的电路集成导致漏电荷和高发热量问题；大量的NP问题在电子计算机上无法有效的求解；信息安全面临着威胁等等。为了解决这些问题,我们需要寻找到新的计算机模型。在许多新型计算机模型中,量子计算机是最值得人们关注的一种。量子计算机是利用量子的物理特性进行计算的计算机：量子计算机通过对量子叠加态的酉演化,可以实现高度的并行计算,从而对大量经典算法进行指数级的加速。著名的量子算法类型有：基于量子傅里叶变换的量子算法,基于无结构数据库搜索的量子算法,基于量子行走的量子算法等。其中量子行走是经典随机行走在量子计算中的对应,又分为离散量子行走和连续量子行走,本文重点研究离散量子行走。离散量子行走的研究方向从总体上可以分为四类：量子行走体系结构研究；量子行走算法研究；量子行走通用性研究；量子行走的逻辑实现研究。本文将工作重心放在量子行走算法和量子逻辑实现的研究上,从如何优化基于量子行走的搜索算法和实现各种数据结构的量子行走算法着手,取得了一定的研究成果,具体如下：1)本文基于RSE范式的演化过程提出了新的R eed-Muller展开式算法。以往的量子可逆逻辑综合算法必须要得到全部真值表信息,而本文提出的展开式算法可以将带大量无关项的电路真值表快速转化为Reed-Mulle r展开式。在对某个特定的量子电路进行逻辑综合时,往往不能避免带有无关项,因此本文提出的量子可逆逻辑综合算法更加具备实用性。2)本文提出了低开销的量子比较器电路。在量子计算中,往往会需要进行Oracle操作,判定目标态的值,这个操作是量子计算中分析查询复杂度的原子操作,所以Oracle操作本身的效率需要慎重考虑。在所有的判定计算中,比较是最常用的一种,因此实现量子比较器非常重要。本文提出的算法巧妙的利用编码电路来实现比较器,比以前提出的算法大大降低了电路的开销。3)本文提出了基于NCP门库的一维量子行走可逆逻辑电路实现方案,根据一维量子行走的特点,将电路划分为投掷量子硬币和根据量子硬币进行随机行走的S操作两个部分；详细分析了S操作,并对S操作进行了数学建模,巧妙的利用可控加减电路实现了S操作。本文提出的电路描述了一维量子行走的最基本操作,并且将其模块化,使得一维量子行走算法从理论到实现前进了一步；利用原始递归给出了一维量子行走中每一步的数学表达式,便于以后更加深入的对一维量子行走算法的研究。在此基础上,本文给出了多维格上的量子行走可逆逻辑综合电路和图上量子行走可逆逻辑综合电路。4)本文详细讨论分析了Grover搜索算法。针对Grover搜索算法在部分数据库上无法进行搜索的问题,提出了改进均值反演算子的方法,提高了Grover搜索算法在实际数据库搜索问题中搜索到目标态的效率。Grover搜索算法在运行之前需要先获得搜索目标的数量,否则无法计算出迭代的次数。针对这一问题,本文提出了迭代次数自适应的Grover搜索算法,在Oracle算子和均值反演算子之间嵌入了一个相位判断的算子,通过判断相位和的符号是否发生变化来决策是否停止算法的迭代。本文提出的算法效率比已有的改进算法要好,只需要多一次Oracle查询。并且本文提出的算法在较低的搜索空间情况下有效的改进搜索概率。5)本文给出了量子行走模拟Grover搜索算法的可扩展图形,并且详细分析了这种量子行走搜索算法的概率。为了求解多目标搜索算法,本文基于超立方体上量子行走框架提出了新的硬币算子,通过对目标节点入边的幅度扩大,增加测量到目标节点的概率,最终解决了多目标搜索问题。利用对邻居节点的二次判定,将搜索概率提高到接近于1。本文还提出将迭代次数自适应算法使用到了量子行走搜索算法上,得到了迭代次数自适应的量子行走多目标搜索算法。在接下来的工作中要继续研究离散量子行走和连续量子行走的性质,研究如何将相位控制技术运用到更多的量子算法中,研究如何用可逆逻辑综合技术逻辑实现其他的量子算法。
【学位单位】：东南大学
【学位级别】：博士
【学位年份】：2015
【中图分类】：O413;TP38
【文章目录】：
摘要
Abstract
专业名词中英文对照
第一章 绪论
    1.1 研究背景和研究意义
    1.2 国内外研究现状
        1.2.1 一维离散量子行走
        1.2.2 图上离散量子行走
        1.2.3 离散量子行走算法
        1.2.4 量子行走的实现
        1.2.5 连续量子行走
    1.3 论文主要贡献和内容安排
第二章 量子行走理论基础
    2.1 量子力学基本假设
        2.1.1 量子力学第一假设
        2.1.2 量子力学第二假设
        2.1.3 量子力学第三假设
        2.1.4 量子力学第四假设
    2.2 一些量子算法
        2.2.1 Deutsch算法
        2.2.2 相位估计算法
        2.2.3 Grover搜索算法
    2.3 量子行走简介
        2.3.1 格上量子行走
        2.3.2 超立方体上的量子行走
        2.3.3 SKW算法
    2.4 小结
第三章 量子行走的逻辑实现
    3.1 带无关项的量子可逆逻辑综合算法
        3.1.1 现有求解RM展开式算法简介
        3.1.2 根据RSE范式直接求解RM展开式
        3.1.3 全项的讨论分析
        3.1.4 矩阵相乘算法与RSE范式求解算法比较
    3.2 格上量子行走量子可逆逻辑综合
        3.2.1 H行走的可逆逻辑电路综合
        3.2.2 多维格无偏量子行走的可逆逻辑电路综合
    3.3 超立方体上量子行走的可逆逻辑综合
    3.4 小结
第四章 迭代次数自适应的多目标搜索算法
    4.1 基于完全图的量子行走搜索算法
    4.2 基于超立方体的多目标量子行走搜索算法
        4.2.1 基于超立方体的新量子行走算子
        4.2.2 基于超立方体的量子行走搜索算法分析
    4.3 迭代次数自适应的搜索算法
        4.3.1 迭代次数自适应的Grover搜索算法
        4.3.2 迭代次数自适应的量子行走搜索算法
    4.4 小结
第五章 总结与展望
    5.1 主要工作总结
    5.2 后续工作展望
附录A 量子行走分析
    a.1 阿贝尔群上的量子行走
    a.2 环上行走的分析方法
    a.3 超立方体上行走分析方法
        a.3.1 超立方体的平均混合时间
        a.3.2 从某个点出发走了t步以后回到出发点的概率
        a.3.3 对超立方体混合时间的分析
    a.4 小结
附录B 基于量子算法的数据库搜索研究
    b.1 用于数据库检索的新均值反演算子的研究
    b.2 用于数据库检索的Oracle算子的可逆逻辑综合研究
0的可逆逻辑电路'>        b.2.1 函数C₀的可逆逻辑电路
1的可逆逻辑电路'>        b.2.2 函数C₁的可逆逻辑电路
        b.2.3 可逆比较器可逆逻辑电路
        b.2.4 可逆比较器代价分析
    b.3 小结
参考文献
致谢
攻读博士学位期间的研究成果

【相似文献】

相关期刊论文 前10条

1 黄帅;马良;;多目标0-1规划的和声搜索算法[J];数学的实践与认识;2012年17期

2 雍龙泉;刘三阳;拓守恒;熊文涛;陈涛;;改进的和声搜索算法求绝对值方程[J];黑龙江大学自然科学学报;2013年03期

3 王慧敏;贺兴时;盛孟龙;;一种改进的和声搜索算法[J];纺织高校基础科学学报;2013年03期

4 冯远静;俞立;冯祖仁;;蚁群协同模式搜索算法及其收敛性分析[J];控制理论与应用;2007年06期

5 刘勇;马良;;非线性极大极小问题的混沌万有引力搜索算法求解[J];计算机应用研究;2012年01期

6 金文梁;;量子搜索算法的多相位关系研究[J];计算机学报;2012年07期

7 张伟;李华天;刘积仁;;线性可采纳搜索算法的充要条件[J];控制与决策;1992年02期

8 李树荣;陈国霞;雷阳;张强;;一种多策略协同的加速和声搜索算法[J];系统科学与数学;2013年10期

9 余鹏;隽志才;;两层应急抢修系统选址问题的核搜索算法[J];计算机应用研究;2013年11期

10 欧阳海滨;高立群;邹德旋;孔祥勇;;和声搜索算法探索能力研究及其修正[J];控制理论与应用;2014年01期

相关博士学位论文 前9条

1 朱皖宁;离散量子行走研究[D];东南大学;2015年

2 孙杰;基于绝热演化的量子搜索算法研究[D];华中科技大学;2013年

3 张映玉;绝热量子搜索算法研究[D];华中科技大学;2011年

4 阎兴頔;组搜索算法研究及其应用[D];华东理工大学;2013年

5 常虹;改进和声搜索算法及其在低碳能源预测中的应用[D];华东理工大学;2013年

6 张欣;基于序列联配的高效可变剪接模式搜索算法和软件[D];上海交通大学;2006年

7 吴昊;云计算环境下智能优化算法及其在SaaS中的应用研究[D];合肥工业大学;2013年

8 王洪福;Grover量子搜索算法理论研究[D];哈尔滨工业大学;2010年

9 金文梁;三维复子空间中的量子搜索和多相位匹配研究[D];西南交通大学;2011年

相关硕士学位论文 前10条

1 刘晓青;高速永磁无刷直流电机的设计及优化[D];南京信息工程大学;2015年

2 许译方;图的极大邻集搜索算法序列及序列终点的性质研究[D];兰州大学;2015年

3 朱航;基于改进和声搜索算法的车间作业调度问题研究[D];南京理工大学;2015年

4 郝雅雄;基于趋向变化的和声搜索算法及其在电力负荷分配中的应用研究[D];兰州大学;2015年

5 张小利;无导数最优化中的模式搜索算法研究[D];河北大学;2015年

6 颜腾威;求解VRP问题的改进和声搜索算法的研究[D];浙江师范大学;2015年

7 高涛;面向众核体系结构的宽度优先搜索算法研究[D];国防科学技术大学;2013年

8 李娜;多目标布谷鸟搜索算法及其应用研究[D];西安工程大学;2015年

9 周诗杰;基于重叠社团划分的道路网络路由搜索算法的研究[D];浙江工业大学;2015年

10 沈冬梅;基于改进引力搜索算法的电力系统机组组合问题的研究[D];东华大学;2016年

本文编号：2843158