资源描述：
《量子grover算法及其应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第36卷第6期数学的实践与认识Vol.36No.62006年6月MATHEMATICSINPRACTICEANDTHEORYJune,2006量子Grover算法及其应用杜治国(华南农业大学信息学院,广东广州510642)摘要:深入剖析了Grover算法,最后将其应用于经典密码学,对序列密码和分组密码等进行了攻击和分析.关键词:量子计算;量子Grover算法;密码学应用1引言现实中许多问题都可归结为搜索问题,如最短路径问题、排序问题、图着色问题、数据库搜索问题及密码中的穷举攻击问题等均属于这类问题.迄今为止,最好的经典(注:此处“经典”与“量子”相对)计算机算法其复杂度O(N)(其中N为搜
2、索空间的大小),1996年[1]1/2Grover提出的量子搜索算法,在量子计算机上对这类问题求解的时间复杂度是O(N),这就是说该算法能够在量子计算机上搜索n比特的数据比在经典计算机上搜索n比特的数据还要快或相当.并且Grover搜索算法是一种对空间进行完全搜索的优化算法.本文我们首先介绍了著名的量子算法—Grover算法,其次对Grover算法进行了深入地剖析,最后将其应用于经典密码,对序列密码和分组密码等进行了攻击和分析.2准备知识2.1量子比特(qubit)量子比特就是复2维Hilbert空间中的一个单位向量.我们知道,一个向量空间的基一旦确定,空间中的每个向量都就唯一的确定.一般
3、取{û0>,û1>}为2维Hilbert空间的一组正规正交基,因此,量子比特可表示为:22aû0>+bû1>,其中a,b∈C(复数域)且ûaû+ûbû=1.2注意:一个空间基的选取不唯一,若取û0>=(û0>+û1>),û1>=22(û0>-û1>).则{û0>,û1>}也为2维Hilbert空间的一组正规正交基.22.2张量积2.2.1空间张量积两个Hilbert空间H和K的张量积是满足下列条件的一个Hilbert空间,记作HáK:1)对任意h1,h2∈H和任意k∈K,有(h1+h2)ák=h1ák+h2ák;2)对任意h∈H和任意k1,k2∈K,有há(k1+k2)=hák1+hák2
4、;3)对任意c∈C,h∈H,k∈K,有c(hák)=(ch)ák=há(ck).收稿日期:2006-04-25314数学的实践与认识36卷这样我们就可以定义多个Hilbert空间的张量积,设H1,H2,…,Hn均为Hilbert空间,则它们的张量积空间为H1áH2á…áHn.2.2.2线性算子张量积设T1∶U→U′,T2∶V→V′为两个线性算子,定义T1和T2的张量积T1áT2为:UáV→U′áV′uávû→T1(u)áT2(v)其中u∈U,v∈V.2.3量子寄存器n个量子位的有序集合称为n位量子寄存器,它的态是n个量子位态的张量积.2.4量子Fourier变换(áL)(áL)设K为一个2
5、维复Hilbert空间,L个K的张量积记为K,对任意ûx>∈K,2L-112Pixy/2L(áL)称变换UQFTûx>=L/2∑eûy>为K上的量子Fourier变换.可以证明量子2y=0Fourier变换是一个酉算子.2.5量子Hadmard变换L=1时的量子Fourier变换,称为量子Hadmard变换,通常记为H.3Grover算法Grover算法[1]是基于无序数据库的搜索算法.对于一个无结构的数据库,最优经典算法的搜索复杂度为O(N),用概率图灵机搜索的期望次数为N/2步.Grover算法的搜索复杂度为O(N),这一算法对经典对称密码的攻击非常有效.下面我们介绍这一算法:n设欲搜
6、索的数据库大小为N,即有N个元素,不妨设N=2,则所搜索的数据库可以用nbit存储.在数学上一个数据库文件可以表示为一个函数f(x),输入x是一个记录的关键字值,f(x)表示的就是对应着关键字取值x的记录.假设每个记录a在文件中出现一次且仅出现一次,数据库搜索问题就是知道x的值,找出与x对应的a.数据库搜索问题可以变为如下一个判定问题:给出一个量子Oracle,它可以计算fa(x),并得到结果:1,若x=afa(x)=(1)0,若x≠a3.1首先构造量子Oracle量子Oracle实际上就是一个酉算子Oa,在计算基{û0〉,û1〉}上定义为:Oaûx〉áûi〉=ûx〉áûiÝfa(x)〉其
7、中ûx〉是一个n-qubit的态(或寄存器),ûi〉是一个1-qubit的态(或寄存器),á为张量积符号,Ý为mod2加法.因此通过制备初始态ûx〉áû0〉,并测量第二个量子寄存器是或û0〉,来判断x是或不是搜索问题的解.1因为若选择ûi〉=(û0〉-û1〉),则21f(x)1Oaûx〉á(û0〉-û1〉)=(-1)aûx〉á(û0〉-û1〉)226期杜治国:量子Grover算法及其应用315为简便起见,略去第二个寄存器
