论文摘要
通信一直是一个重要的问题,存在通信,就必然存在信息的交流。但是很多信息只要通信的双方知道,而不需要第三方知道,因此产生了密码技术,伴随着科技的发展,密码技术也越来越完善。但同时对密码的攻击也越来越强大。量子论是上世纪科学史上一个重大的发现,量子力学、信息论和计算机科学相结合,形成了量子信息学。创造出了“绝对安全的密钥”“隐形传态”等理论;构造出了“分解大数质因子”“未加整理的数据库搜索”等量子算法。并且利用理想中的量子计算机,可以实现大规模的并行计算,产生经典计算机不可比拟的信息处理功能等。在经典计算中,搜索问题是一个很难的问题,要是在一个数据库中搜索目标元素,需要的搜索步骤是O（N）,其中N（N=2n）为数据库中元素的个数,n表示数据库的位数,搜索步骤随n指数增长。上世纪九十年代,Lov K.Grover提出了一种随机数据库搜索的量子算法,即“未加整理的数据库搜索”。称为Grover量子搜索算法,这个搜索算法利用了量子态的叠加性和量子计算的并行性,其可以把搜索问题从经典的O（N）步减少到O（（?））步,显示出了量子加速。本文的研究就是基于Grover量子搜索算法和量子部分搜索（quantum partial search）,对含有两个目标块的部分搜索问题作了深入地研究。从最基本的含有三个目标的情况入手,首先分析了,三个目标被非平均的分配在两块中的情况。进一步分析了含有t个目标的数据库,所分的K块中有两块含有目标,其中有一个含有一个目标的情况,得到了限制搜索次数的条件方程2（K-t）cos2α+2（Kt-K-t）cos（（?））-t（K-4）=0。通过数值计算得知参数K和t与查询次数的关系。在此基础上,更进一步研究了当数据库中的目标个数t一定时,一块中含有z个目标,另一块含有t-z个目标,通过计算得到限制搜索次数的条件方程:（2zK-2t）cos（2α（?））+（2（t-z）K-2t）cos（2α（?））-t（K-4）=0。通过数值计算可知参数z与搜索次数的关系,进一步可以得出两个目标块中所包含的目标个数的差t-2z对查询次数的关系,从而找到搜索次数最少的目标的分配方式。最后把Grover搜索的量子加速应用到对分组密码的不可能差分攻击中,提高攻击的效率。