《5.Grover algorithm.ppt》由会员分享，可在线阅读，更多相关《5.Grover algorithm.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Grover AlgorithmQuantum Computation and Quantum informationQuantum Computation and Quantum information2009.04.13Grover搜索问题：从一个问题的解空间中找出正确解的问题。一、搜索问题及其密码学背景一、搜索问题及其密码学背景 密码学意义:（1）密钥的求解问题；（2）将一个文件的数字签名伪造成另一份文件的数字签名问题。（3）搜索问题：从一个问题的解空间中找出正确解的问题。一、搜索问题及其密码学背景一、搜索问题及其密码学背景 密码学意义:（1）密钥的求解问题；（2）将一个文件的数字签名伪
2、造成另一份文件的数字签名问题。（3）搜索问题：从一个问题的解空间中找出正确解的问题。一、搜索问题及其密码学背景一、搜索问题及其密码学背景（续（续1）共有N个可能解只有1个真解一般性方法：-逐个测试(穷举攻击)假设：结论：逐个测试方法的计算复杂性平均是 N/2.问题：量子计算机的强大并行计算能力能否降低搜索问题的计算复杂性？答案：当搜索问题只有 1 个真解时，Grover算法的 计算复杂性为 ，成功率接近于1。问题：量子计算机的强大并行计算能力能否降低搜索问题的计算复杂性？这就是Grover量子搜索算法。该算法由Grover于1995年提出，在量子计算领域中的影响仅次于Shor算法。Yes！N
3、是解空间的点数一、搜索问题及其密码学背景（续一、搜索问题及其密码学背景（续2 2）二、搜索问题的数学模型二、搜索问题的数学模型 具体方法：将每个密文脱密，并检测脱密结果是否为已知的明文 密钥搜索问题的数学模型：假设已知若干个明文及对应的密文,密钥空间为K.则可定义判决函数 f:K0,1,使对所有可能密钥 k,都有若 k 能通过脱密测试;若 k 不能通过脱密测试。搜索问题都可归结为在判决函数f:0,1函数 f 称为一个Oracle(数据库、神谕、预言)对每个输入都可计算出来的条件下,从 N 元的可能解集合中找出一个满足f(x)1的点 x 的问题。二、搜索问题的数学模型（续二、搜索问题的数学模型（
4、续1 1）三、三、Grover量子搜索算法量子搜索算法（条件：真解的个数已知）（条件：真解的个数已知）Search problemThe quantum search algorithm solves the following problem:Given a search space of size N,and no prior knowledge about the structure of the information in it,we want to find an element of that search space satisfying a known property.Ho
5、w long does it take to find an element satisfying that property?Classically,this problem requires approximately N operations,but the quantum search algorithm allows it to solved using approximately operations.量子搜索问题量子搜索算法解决如下问题：给定大小为给定大小为N的搜索空间，没有关于它结构的搜索空间，没有关于它结构信息的先验知识。希望找到这个搜索空间信息的先验知识。希望找到这个搜索空
6、间中的满足已知性质的一个元素。要找到一中的满足已知性质的一个元素。要找到一个满足条件的元素需要多久。个满足条件的元素需要多久。经典情形，这个问题需要大概N次操作，但是量子搜索算法可以用大概次操作解决。Grover algorithmThe quantum search algorithm is proposed by Grover in 1995.When there is only one solution of it,the computation complexity is The probability of success is closely to 1.Grover algorit
7、hm该算法由Grover于1995年提出，在量子计算领域中的影响仅次于Shor算法。当搜索问题只有 1 个真解时，Grover算法的计算算法复杂性为 ，成功率接近于1。Basic principlesSuppose we wish to search through a search space of N elements,For conveniently we assume N=2n And that the search problem has exactly M solutions.A parcicular instance of the search problem can conve
8、niently be represented by a function f,which takes as input an integer x,in the range 0 to N-1.By definition,f(x)=1 if x is a solution to the search problem,and f(x)=0 if x is not a solution to the search problem.基本原理假设在N个元素的空间中搜索，为方便起见，假定N=2n，且搜索问题恰好有M个解，这个问题的特例可以方便地表示为一个输入x的函数f(x)，x是从0到N1的整数，f的定义是
9、：若x是搜索问题的一个解，则f(x)=1，而若x不是解，则f(x)=0。Suppose we are supplied with a quantum oracle-a black box,the action of the oracle may be written:We say that the oracle marks the solutions to the search problem,by shifting the phase of the solution.For an N item search problem with M solutions,it turns out that
10、 we need only apply the search oracle times in order to obtain a solution,on a quantum computer.设有一个量子oracle可以识别搜索问题的解。Oracle的作用可以写成：我们说oracle通过改变相位，标识了搜索问题的解。对有M个解的N元搜索问题，实际上为得到一个解，只需要在量子计算机上应用搜索oracle次。It seems as though the oracle already knows the answer to the search problem;what possible use c
11、ould it be to have a quantum search algorithm based oupon such oracle consulations?!The answer is that there is a distinction between knowing the solution to a search problem,and being able to recognize the solution;the crucial point is that it is possible to do the latter without necessarily being
12、able to do the former.表面上看Oracle好象已经知道了搜索问题的解，这种基于oracle查询的量子搜索算法能有什么用呢？答案是：知道知道搜索问题的解和能识别识别解是有区别的，关键在于有可能在不需要知道解的情况下识别解。基基 本本 假假 设设(2)判决函数：f:0,1n 0,1k0,1n 是真解f(k)1(1)解空间大小：N2n(3)判决方法：(4)真解的个数为 MGrover量子搜索算法量子搜索算法 step1step1：Preparation of superposition state:step2：compute parallelly step3step3：Z op
13、eration transformTh effection of step3:only the amplitudes of solution are negative三、三、Grover量子搜索算法量子搜索算法 第第一一步步：初始化：产生一个等幅度的状态叠合:第二步：第二步：完成对判决函数的并行计算 第第三三步步：对最后分量做“Z 操作”变换，标出真解第三步的效果:只有真解的幅度才是负值 step4：preform D transform on the first component of|x,f(x)-augmentthe probability of solution b correspo
14、nd to the state|b,1.where D is described by the matrix 第四步：第四步：对|x,f(x)的第一分量执行 D 变换 -增大真解 b 对应的状态|b,1的出现概率。其中 D 变换的变换矩阵 为:即：幅度的变化规律为ai 是|i的幅度幅度的“平均值”如果幅度的“平均值”0 若若ai0,则则 若若ai0,则则第四步的效果：真解的出现概率变大！第三步的效果变换矩阵刻画函数关系刻画step5：repeatly preform step3 and step4 k times，and measure the state,we will get the re
15、sult|x,1,and output x as a real solution.attention:(1)the value k must be determined beforhand (2)only compute f(x)one time in the whole algorithm!第第五五步步：重复执行第三步至第四步 k 次后进行观察，得到观察结果|x,1,并将 x 作为真解输出。注意注意:(1)迭代次数 k 的值必须预先设定;(2)整个算法只计算 f(x)一次!效果：真解的幅度变负效果：真解的幅度变大Grover iteration -step3 and step 4 (1)th
16、e effect of the composite of step 3 and step4-Grover iteration?(2)can the D transform in step 4 be preform efficiently？Grover 迭代迭代 -step3 and step 4(1)Grover 迭代迭代 第三、四步复合的实际效果？(2)第四步中的 D 变换能否有效实现？(1)The amplitudes of Grover iteration If all ax0,The amplitudes ax of Real solution x argumentAverage am
17、plitudesAmpltitude（2）D transform transform matrix That is：R transform make the amplitude of nonzero negative.Theorem 1 DWRW,here W is n dimention Fourier transform,R transform is described as follows:That is Compute complexity is：O(2n)The correspond relation of the basis provenoteasSo DWRWover some
18、problem:(3)How to determine the value of k？(4)the probability of success of Grover algorithm？几个问题几个问题:(3)迭代次数 k 的值如何设定？(4)Grover算法的成功率是多少？supposed the quantum state after perform step2 isthe iteration times of Grover algorithmNote the quantum states after mth iteration is#i:f(i)1M,so as Th2 supposed
19、 the state after mth Grover iteration is So here prove induction to m.if m0，so When m0,Th 2 is rightProve:supposed th2 is right when m happens ，now proved that it is the truth when m1 happens.So soprove that is Th2 is right when m+1 happensoverTh2 is the truth from Th2,we know that observe,the proba
20、bility of the real solution isThe probability of observe a real solution iswhen,the probability 1hereGrover algorithm of m grover iteration may find a solution with the probability sin(2m+1)2Here sin2 M/2nThe preriod of sin2z is/2The times of Grove iteration is The probability of success is close to
21、 1Grover算法的意义:（2）由于Grove算法中只执行一次加密测试(即计算 f(x)，且Grove迭代的计算复杂性远小于加密测试的计算复杂性。（1）说明对密钥比特个数为n的密码算法的穷举攻击的计算复杂性为计算复杂性为 次Grove迭代。在量子计算机上穷举攻击128比特密钥的密码算法就远小于在经典计算机上穷举攻击64比特密钥的密码算法。128比特的密钥量是比特的密钥量是不可靠不可靠的的。(1)the initial state of Grover algorithm is not an equal stateOther problem:Will the effect be better？(
22、2)when the value of the solution number M is unknown,how to set the interation times k?(3)Can we improve Grover algorithm？(1)Grover迭代的初始态不是等幅度态其它问题其它问题:时效果是否有可能更好？(2)真解的个数 t 不知道时怎么办？(3)Grover算法是否还能够得到改进？Other problems:(1)the initial state of Grover algorithm is not an equal stateWill the effect be b
23、etter？conclusion：impossible！the amplitude of the initial state is more equal,more better！结论：不可能！初始态的幅度越均匀越好！(1)Grover迭代的初始态不是等幅度态时效果是否有可能更好？其它问题其它问题:Other problems:(2)when the value of the real solution M is unknown,how to set the interation times k?-try t one by one Step1 supposed a value of t；Step
24、2 perform Grover algorithm，observe a result.Step3 test the result is right or not.if it is right，the algorithm is over；if it is not right，perform Step4;Step4 supposed another value of t，perform Step2 to Step3.-穷举 t Step1 假设出 t 的一个值；Step2 按假设的 t 执行Grove算法，并观察到一个结果；Step3 检验所得到的值是否是真解。如果是真解，则算法结束；如果不是真
25、解，则执行Step4;Step4 假设出 t 的另一个值，并返回执行Step2至Step3。-穷举策略:先测试最大可能者,再测试次大可能者,.(2)真解的个数 t 不知道时怎么办？其它问题其它问题:(3)Can we improve Grover algorithm？Other problems:conclusion:impossible to improve essentially,that is to say：for any interation algorithm with the probability of success 0.5，the compute complexity is
26、more than 结论:不可能得到本质的改进。即：对于任何一个成功率0.5的量子迭代算法，其计算复杂性都大于 意义:（1）没有对所有密码算法都有效的、求解密钥的、多项式时间的通用量子计算算法。（2）量子计算机不能对序列密码、分组密码带来致命的威胁。（3）Grover算法对加密算法的影响只是密钥长度必须加倍！(3)Grove算法还能否得到改进?其它问题其它问题:Grover algorithmAll0state Equal stateComputeThe Decision functionparallelMake theamplitude of a real solution negativeQFTThe amplitude of no-zero oppositeobservestep4QFT小结：Grover算法的流程图全0的经典态等幅度的量子态制备判决函数的并行计算真解的幅度反号量子富立叶变换非零点的幅度反号量子富立叶变换观察第四步 Thank you!