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