学位论文 > 优秀研究生学位论文题录展示

集合运算的量子算法设计及其应用

作　者: 丁从宝
导　师: 庞朝阳
学　校: 四川师范大学
专　业: 理论物理
关键词: 量子计算量子算法量子集合运算量子模式识别
分类号: O413
类　型: 硕士论文
年　份: 2009年
下　载: 98次
引　用: 0次
阅　读: 论文下载

内容摘要

量子计算与量子信息是涉及物理学、计算机科学、数学以及信息科学等多个学科的新兴综合性交叉研究领域。量子计算和量子计算机的思想最早由著名的物理学家Feynman提出,它是量子力学理论和经典计算理论完美结合的产物。由于其强大的计算能力及广阔的应用前景,使得其在国际学术界以及政府科研机构中引起巨大的兴趣,得到快速发展。量子信息技术是量子特性如:量子相干性、非局域性、纠缠性、不可克隆性等在信息科学领域的应用,它能有效突破现有信息技术面临的困难,具有很多新的性能。例如:1994年Peter W Shor提出的因子分解算法可以在量子计算机上有效求解大数质因子分解问题,而这个问题对于经典计算机却是非常困难的以至于成为现在广泛使用的RSA密码系统的基础。这直接证明了量子计算机具有经典计算机无法比拟的计算优势。在量子计算的研究中,计算性能的优越性主要体现在算法的有效性上。目前为止,被公认的最具代表性的量子算法有Shor的大数质因子分解算法以及Grover提出的数据库搜索量子算法。由于Grover搜索算法只能进行简单问题搜索,不能完成复杂的计算,使得其在实际应用中具有很大的局限性。此外,任何数据信息在进行处理之前都必须先将其装载到计算机寄存器中,从而进一步完成计算。但是,在经典计算机中I/O设备的运行速度对于任意一个经典算法都是一个效率瓶颈。经典的计算过程是经由I/O设备把数据一个一个的装载到寄存器中,再将计算结果一个一个的输出。如果是处理海量的数据,这种输入输出方法的效率是极其低的,但这在经典计算理论中却又是无法克服的。另外,量子计算机只能处理量子态而不能直接处理经典数据,所以必须有一个针对量子计算机的数据存储方案。本文将介绍数据存储的量子方案(QLS方案),它可以有效解决这一效率瓶颈问题。集合运算是科学技术很多领域的基础,像数据库操作、信号处理、图象压缩等等都可最终归结为对集合的操作。但是对于像包含了高维无序向量的集合,要对其进行有效快速的集合运算,在经典电子计算机上是困难的。因此,我们就需要新的原理和新的算法来有效操作集合。在本文中我们针对上面的困难提出了一个新的算法-量子集合算法并且给出了该算法在信号处理问题中的一个有效应用。本文主要包括三个部分:第一部分回顾了量子计算的起源及研究进展,研究和分析了量子计算的基本原理和相关概念。重点研究和分析了Shor算法、Grover算法,Boyer算法等已知的重要量子算法。第二部分介绍了旋转子空间方法以及经典数据与量子存储器关联方案,并且在此基础上结合Grover搜索算法设计出了量子集合算法,同时对该算法进行了计算复杂性论证。最后,分析对比了G general迭代和Grover迭代的优点和不足。第三部分给出了量子集合算法在信号处理中的一个应用即:量子模式识别。从包含了干扰信号的海量数据中实时地识别出目标信号是现代信号处理技术的关键。如果待处理的数据数量过大对于现代信号处理技术是困难的,但是从我们提出的量子模式识别方案中可以看出,量子计算机能有效解决这一难题。

全文目录

摘要  3-5
Abstract  5-10
第一章引言  10-16
  1.1 量子计算的起源及国内外研究现状分析  10-13
  1.2 本课题研究的目标、内容及拟解决的关键问题  13-14
  1.3 本课题拟采取的研究方法及研究意义  14
  1.4 本章小结  14-16
第二章量子计算基础  16-22
  2.1 量子比特和基本量子比特门  16-18
  2.2 量子态叠加性原理及量子并行性  18-19
  2.3 量子态的演化及幺正算符  19-20
  2.4 纠缠与量子测量  20-21
  2.5 本章小结  21-22
第三章基本量子算法  22-33
  3.1 早期相对“black box”加速的量子算法  22-24
    3.1.1 Deutsch 量子算法  22-23
    3.1.2 Deutsch-Jozsa 算法  23-24
  3.2 Shor 量子算法  24-28
    3.2.1 量子Fourier 变换  25-26
    3.2.2 Shor 大数因子分解算法  26-27
    3.2.3 量子求阶算法  27-28
    3.2.4 量子Fourier 变换的一些应用  28
  3.3 Grover 量子搜索算法  28-30
  3.4 Boyer 算法  30-31
  3.5 本章小结  31-33
第四章数据存储的量子方案（QLS）和旋转子空间理论  33-42
  4.1 数据存储的量子方案（QLS）  33-37
  4.2 旋转子空间理论  37-41
  4.3 本章小结  41-42
第五章量子集合运算  42-51
  5.1 经典求集合交集算法  42-43
  5.2 数据结构与幺正操作  43-45
  5.3 程序1：搜索查询集合C= A ∩B 中的一个元素  45-46
  5.4 关于C= A ∩B 运算的量子算法  46-47
  5.5 求集合交集运算的量子算法性能分析  47-50
  5.6 本章小结  50-51
第六章量子集合算法的应用——量子模式识别  51-57
  6.1 多模式识别结构  52-53
  6.2 量子多模式识别  53-56
    6.2.1 构建数据结构与幺正算符  53-55
    6.2.2 进行多个目标模式识别的量子算法（多模式识别量子算法）  55-56
  6.3 本章小结  56-57
第七章结论  57-60
参考文献  60-66
致谢  66-67
在校期间的科研成果  67

集合运算的量子算法设计及其应用

内容摘要

全文目录

相似论文