Grover算法的改进及其应用

论文摘要

量子计算是利用微观粒子进行信息处理和存储的一门新的交叉学科。研究结果表明量子计算的并行计算能力在某些方面优于经典计算。例如Grover算法能在O(N1/2)步解决函数的逆问题。相比于经典算法,该算法的算法速率得到了平方增长。Grover算法不仅有强大的并行计算能力,而且有广泛的应用前景,因此受到广大研究者的密切关注。本文主要研究了Grover算法的改进及其应用。从降低Grover算法量子线路的角度出发,在以往研究工作的基础上,深入分析了Grover算法,并根据需求提出两种改进算法。本文的主要工作如下:（1）在Grover算法的基础上,本文将经典验证与该量子算法结合,提出了一个概率型的Grover算法（Probabilistic Grover Algorithm,PGA）。为了降低Grover算法的量子线路复杂度,本文首先设计了一个经典验证函数。然后设计了PGA的量子线路、算法步骤和算法几何过程。最后从量子线路、几何过程和算法过程这三个方面分析了算法的性能,并比较了四个算法的算法性能。分析结果表明,PGA应用多次测量和经典函数验证,经过O(πN1/2/8)步迭代能以大于1/2的概率找到解。PGA的量子线路少于Grover算法的量子线路,其量子线路复杂度是O(πN1/2/8)。（2）子集和问题是密码学中一类重要的困难性数学问题,即NPC（Non-deterministic Polynomial Complete）问题。本文将概率型的Grover算法（PGA）应用到子集和问题上,并结合经典中间相遇算法（Meet-in-the-middle Algorithm,CMMA）,提出一个子集和问题的概率型量子中间相遇算法（Probabilistic Quantum Meet-in-the-middle Algorithm,PQMMA）。首先利用CMMA思想对子集和问题中的元素进行划分。然后利用CMMA思想设计新的oracle函数。最后将新的oracle函数应用到PGA中,从算法步骤和几何过程这两个方面设计了PQMMA。分析结果表明,PQMMA应用多次测量和经典验证,以算法成功率为代价,减少了O(π2（n-1）/3/8)个G量子线路。PQMMA的量子线路复杂度是O(π2（n-1）/3/8)。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景
•   1.2 研究现状
•   1.3 主要贡献
•   1.4 组织结构
• 第2章 量子计算基础
•   2.1 引言
•   2.2 数学基础
•     2.2.1 向量
•     2.2.2 线性算子
•     2.2.3 简单运算
•   2.3 原理基础
•     2.3.1 量子基本单元
•     2.3.2 量子线路
•     2.3.3 量子力学假设
•   2.4 基本量子算法
•     2.4.1 量子并行性
•     2.4.2 Deutsch算法
•     2.4.3 Grover算法
•   2.5 本章小结
• 第3章 概率型的Grover算法（PGA）
•   3.1 引言
•   3.2 PGA的算法思想
•   3.3 PGA的算法过程
•     3.3.1 oracle
•     3.3.2 算法步骤
•     3.3.3 算法几何描述
•     3.3.4 算法性能分析
•   3.4 算法性能比较
•   3.5 本章小结
• 第4章 PGA在子集和问题上的应用
•   4.1 引言
•   4.2 子集和问题描述
•   4.3 概率型量子中间相遇算法的算法思想
•   4.4 概率型量子中间相遇算法的算法过程
•     4.4.1 oracle
•     4.4.2 算法步骤
•     4.4.3 算法几何描述
•     4.4.4 算法性能分析
•   4.5 算法性能比较
•   4.6 本章小结
• 第5章 总结与展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果

文章来源

类型: 硕士论文

作者: 马利芬

导师: 王平

关键词: 量子并行计算,算法,经典验证,子集和问题

来源: 深圳大学

年度: 2019

分类: 基础科学,信息科技

专业: 物理学,计算机硬件技术

单位: 深圳大学

分类号: TP38;O413

总页数: 69

文件大小: 3261K

下载量: 36