5.grover algorithm

《5.grover algorithm》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GroverAlgorithmQuantumComputationandQuantuminformation2009.04.13Grover搜索问题：从一个问题的解空间中找出正确解的问题。一、搜索问题及其密码学背景密码学意义:（1）密钥的求解问题；（2）将一个文件的数字签名伪造成另一份文件的数字签名问题。（3）……搜索问题：从一个问题的解空间中找出正确解的问题。一、搜索问题及其密码学背景密码学意义:（1）密钥的求解问题；（2）将一个文件的数字签名伪造成另一份文件的数字签名问题。（3）……搜索问题：从一个问题的解空间中找出正确解的问题。一、搜索问题及其密码学背景（续1）共有N个可能解

2、只有1个真解一般性方法：----逐个测试(穷举攻击)假设：结论：逐个测试方法的计算复杂性平均是N/2.问题：量子计算机的强大并行计算能力能否降低搜索问题的计算复杂性？答案：当搜索问题只有1个真解时，Grover算法的计算复杂性为，成功率接近于1。问题：量子计算机的强大并行计算能力能否降低搜索问题的计算复杂性？这就是Grover量子搜索算法。该算法由Grover于1995年提出，在量子计算领域中的影响仅次于Shor算法。Yes！N是解空间的点数一、搜索问题及其密码学背景（续2）二、搜索问题的数学模型具体方法：将每个密文脱密，并检测脱密结果是否为已知的明文密钥搜索问题的数学模型：假设已

3、知若干个明文及对应的密文,密钥空间为K.则可定义判决函数f:K→{0,1},使对所有可能密钥k,都有若k能通过脱密测试;若k不能通过脱密测试。搜索问题都可归结为在判决函数f:Ω→{0,1}函数f称为一个Oracle(数据库、神谕、预言)对每个输入都可计算出来的条件下,从N元的可能解集合Ω中找出一个满足f(x)＝1的点x的问题。二、搜索问题的数学模型（续1）三、Grover量子搜索算法（条件：真解的个数已知）SearchproblemThequantumsearchalgorithmsolvesthefollowingproblem:GivenasearchspaceofsizeN,

4、andnopriorknowledgeaboutthestructureoftheinformationinit,wewanttofindanelementofthatsearchspacesatisfyingaknownproperty.Howlongdoesittaketofindanelementsatisfyingthatproperty?Classically,thisproblemrequiresapproximatelyNoperations,butthequantumsearchalgorithmallowsittosolvedusingapproximatelyo

5、perations.量子搜索问题量子搜索算法解决如下问题：给定大小为N的搜索空间，没有关于它结构信息的先验知识。希望找到这个搜索空间中的满足已知性质的一个元素。要找到一个满足条件的元素需要多久。经典情形，这个问题需要大概N次操作，但是量子搜索算法可以用大概　　次操作解决。GroveralgorithmThequantumsearchalgorithmisproposedbyGroverin1995.Whenthereisonlyonesolutionofit,thecomputationcomplexityisTheprobabilityofsuccessiscloselyto1.

6、Groveralgorithm该算法由Grover于1995年提出，在量子计算领域中的影响仅次于Shor算法。当搜索问题只有1个真解时，Grover算法的计算算法复杂性为，成功率接近于1。BasicprinciplesSupposewewishtosearchthroughasearchspaceofNelements,ForconvenientlyweassumeN=2nAndthatthesearchproblemhasexactlyMsolutions.Aparcicularinstanceofthesearchproblemcanconvenientlyberepresen

7、tedbyafunctionf,whichtakesasinputanintegerx,intherange0toN-1.Bydefinition,f(x)=1ifxisasolutiontothesearchproblem,andf(x)=0ifxisnotasolutiontothesearchproblem.基本原理假设在N个元素的空间中搜索，为方便起见，假定N=2n，且搜索问题恰好有M个解，这个问题的特例可以方便地表示为一个输入x的函数f(x)，x是从0到N－