xxx学院

量子搜索算法在数据库中的应用

目录
摘要 1
Abstract 2
第一章 引言 3
第二章任务内容 5
2.1设计部分 5
2.2理论要求 5
第三章量子计算中的基本概念 6
3.1比特和昆比特 6
3.2量子平行 7
3.3量子纠缠 7
第四章量子算法 9
4.1 shor算法介绍 9
4.2 Grover算法的介绍 10
4.3 Grover算法的讨论分析 11
4.4 Grover算法与传统搜索算法在数据库中的应用 13
4.4.1 Grover算法在传统无序数据库中的实现 13
4.4.2 Grover算法与传统搜索算法在数据库应用中的比较 14
4.5 Grover算法的评价 15
4.5.1优点 15
4.5.2缺点 15
第五章结束及展望 17
参考文献 18

摘要

介绍Grover算法的基本框架,叙述了量子算法中非结构化搜索算法的设计思想。在Grover算法中,结合量子的物理特性,分析了Grover算法的优缺点。解释Grover算法有效的原因和适用的场合,讨论了影响算法效率的因素。在上述论述的基础上对量子搜索算法与传统搜索算法进行了比较和分析,并在一些例子中说明比较得出的结论，总结了量子搜索算法在数据库实际应用中的优点以及发展前景

关键词: 量子搜索算法,Grover算法,量子叠加态

Abstract
 
In this paper, an important idea of devising a quantum algorithm is introduced, based on the description and analysis of two classes of quantum search algorithms, i.e. the unstructured search algorithms and structured search algorithms. Some qualities of Grover’s search algorithm, which is the representation of the unstructured search algorithms are introduced and summarized, by analyzing its peculiar complexity, completeness, sensitivity to the errors in the mappings, and its advantages and disadvantages. On introducing structure-based search algorithm, the Tad Hogg’s series of search algorithms are referred to. They can be summarized into one universal algorithm framework, which can be separated into two parts, i.e., the problem-independent mapping and phase rotation matrix. This paper places emphasis on analyzing one of the phase adaptation strategies, and interprets how it works and what can make it more efficient. Some other factors affect the algorithm are also discussed more generally. Finally, based on the comparison and analysis of classical search algorithm and the quantum one, the thoughts behind various quantum search algorithms are illustrated.

Keywords : quantum search algorithm; geometric interpretation of Grover’s iterative procedur

第一章 引言
计算机技术把我们带入了一个崭新的“信息时代”，给我们的工作和生活带来了巨大变化。发明计算机的先辈们没有料到计算机能成为人们生活中不可或缺的工具；他们也难以想象计算机诞生以来发生的惊人变化。计算机芯片的集成度以大约每十八个月就提高一倍的速度指数增长（摩尔定律），计算机芯片的集成度在不久的将来就有望达到原子分子量级(~10-10m)。但是量子力学告诉我们，在这样的微观领域内，量子效应会影响甚至完全破坏芯片功能。
量子力学是本世纪自然科学的最重要的成就之一。量子力学的观念同我们日常生活的经验有很大的不同。根据量子力学的原理，一个量子微观体系的状态是由一个波函数描写，而不再是由粒子的位置和动量描述。这个波函数决定了粒子出现在空间某一点或者具有某一动量的几率。对一个体系进行某一力学量的测量时，不再象经典粒子那样具有确定的值，而只能取某些特定的值。在经典力学中，对体系的测量不会改变体系的状态，至少在理论上可以构造理想测量实验，使得体系的状态在测量前后不发生变化。而在量子力学中，测量一般要改变体系的波函数，即体系的状态。经典体系的状态随时间的变化遵从牛顿定律，而量子体系的状态随时间的变化遵从Schroedinger方程。根据量子力学中的海森堡测不准原理，当位置定的很准时，粒子的动量就不会定准。将海森堡测不准原理应用于计算机的芯片问题中，当密度很大时，D x很小时，D p就会很大，电子就不再被束缚，就会有量子干涉效应。这种量子干涉效应会完全破坏芯片的功能。 是不是说量子力学就一定是计算机技术的大敌呢？对于现有计算机技术，量子力学的限制确实是一个障碍。但是应用量子力学的原理直接进行计算，不但可以越过量子力学的障碍，而且可以开辟新的方向。
量子计算机就是以量子力学原理直接进行计算的计算机。1982年美国的R. Feynman提出了把量子力学和计算机结合起来的可能性。1985年英国牛津大学的D. Deutsch进一步阐述了量子计算机的概念，并且证明了量子计算机比经典图灵计算机具有更强大的功能。Shor证明了量子计算机会对现有的社会和国民经济以及国防产生潜在的威胁。目前大量的网络保密是使用“RSA公开码”的密码技术。想要破译这种密码，就要对大数分解质因子。分解一个大数的质因子是极其困难的。按照现有的理论计算，分解一个400位数的质因子，用目前最先进的巨型计算机也需要用10亿年的时间，而人类的历史才不过几百万年。然而量子计算机概念的出世，严重动摇了RSA公共码的安全性。1994年，美国的P.W.Shor利用量子计算机理论证明，一个N位大数的质因子分解只需用N的多项式的时间而不是以前所认为的N的指数次的时间。利用量子计算机分解一个400位大数仅仅需要不到一年的时间！Shor的工作引起了科学家们巨大的热情和兴趣。1995年，美国Grover证明在搜索问题上量子计算机比经典计算机优越。从没有排序的含N个数据的数据库中搜索一个确定的数据，用经典计算机平均需用N/2次运算，利用量子平行计算方法，只需 次运算。科学家还证明了任何在经典计算机上多项式可解的问题在量子计算机上也必定只需多项式次操作就可以完成。也就是说量子计算机解决任何问题上都至少不比经典计算机差。
什么使得量子计算机会有如此优越的性质呢？量子计算机和经典计算机有什么区别呢？量子计算机也由存储器和逻辑门网络组成。但是量子计算机的存储内容和逻辑门与经典计算机却有所不同。对经典图灵计算机来说，信息或者数据由二进制数据位存储，每一个二进制数据位由0或1表示。在量子力学中，我们可以用自旋或者二能级态构造量子计算机中的数据位。与经典计算机相区别，我们称之为量子位(q－bit)。

第二章任务内容
2.1设计部分
创建一个含有4个元素的无序数据库,并通过Grover算法进行搜索计算。
2.2理论要求
通过对量子本身的物理特性的学习以及对Grover算法的深入了解,并对传统的搜索算法加以比较和总结。

第三章量子计算中的基本概念
3.1比特和昆比特