（信号与信息处理专业论文）grover量子搜索算法的改进及其在图像检索中的应用.pdf

南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索； 可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质 论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 涉密学位论文在解密后适用本授权书。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ 南京邮电大学南京邮电大学 硕士学位论文摘要硕士学位论文摘要 学科、专业：工学 信号与信息处理 研 究 方 向： 量子信息技术 作 者：2009 级研究生张海雄 指 导 教 师：李飞教授 题 目：grover 量子搜索算法的改进及其在图像检索中的应用 英 文 题 目：improvement of grover quantum search algorithm and its application to image retrieval 主 题 词：量子计算；grover 算法；图像检索；特征提取 keywords: quantum computation; grover algorithm; image retrieval; feature extraction 南京邮电大学硕士研究生学位论文 摘要 i 摘摘 要要 以量子并行计算为基础的grover量子搜索算法，对于长度为n的无序数据库搜索，计算复 杂度仅为()on。 grover 量子搜索算法在进行搜索时，随着搜索目标数的增加获得正确结果的概率大幅度 下降，并且当搜索的目标数占数据总数的一半时，无论搜索多少次，所得的概率都为1/2，此 时算法是无效的。本文研究了 grover 量子搜索算法及其改进，并将其应用于图像检索。主要 的研究工作有： 首先，研究了 grover 量子搜索算法，并在经典计算机上模拟实现了量子 grover 算法。 分析了原始 grover 算法存在的缺点，研究了已有三种改进的 grover 算法，在此基础上设计 了一种改进的自适应相位旋转的 grover 量子搜索算法。 其次，研究了基于纹理特征的图像检索，用基于灰度共生矩阵、灰度-梯度共生矩阵和双 树复小波变换的三种方法分别对图像的纹理特征进行了提取。 最后，将改进后的 grover 量子搜索算法用于图像检索。仿真结果表明，该算法在图像检 索中能得到较好的检索效果。 关键词：关键词：量子计算；grover 算法；图像检索；特征提取 南京邮电大学硕士研究生学位论文 abstract ii abstract to search a unordered database with a length of nusing grover algorithm, which is based on the quantum state of parallel computation, the computational complexity is ()on. when search database using grover algorithm, with the increase of target number the probability of obtaining the correct results declines significantly. and when the searching target is half of the total database, the resulting probability is1/ 2, no matter how many times we search, and then the algorithm is invalid. grover quantum search algorithm and its improvement are researched in this paper and applied to image retrieval. the main research works of this dissertation can be summarized as follows: first of all, the grover quantum searching algorithm is investigated and achieved by simulation on classic computer. some problems existing in basic grover searching algorithm are analyzed. and improved adaptive phase rotation grover quantum search algorithm is proposed. in addition, image retrieval based on texture features is studied. image texture features are extracted using three methods. finally, image retrieve based on texture feature is researched and the improved grover quantum searching algorithm is applied to image retrieve. the simulation results show that we can effectively reduce the computational complexity in image retrieve and obtain better retrieval results when we use this algorithm. keywords: quantum counting; grovers algorithm; image retrieval; feature extraction 南京邮电大学硕士研究生学位论文 目录 iii 目目 录录 摘 要 . i abstract . ii 目 录 . iii 第一章 绪 论 . 1 1.1 课题的研究背景及意义 . 1 1.2 本论文的主要研究内容 . 3 第二章 grover 量子搜索算法 . 4 2.1 量子信息论基础 . 4 2.1.1 量子计算基础 . 4 2.1.2 量子逻辑门 . 8 2.1.3 量子并行性 . 10 2.2 grover 量子算法 . 11 2.2.1 基于黑箱的搜索思想 . 11 2.2.2 grover 量子算法搜索步骤 . 12 2.2.3 grover 算法模拟及结果分析 . 14 2.3 本章小结 . 16 第三章 grover 量子搜索算法的改进 . 17 3.1 基于 /2 相位旋转的改进算法 . 17 3.2 基于分段固定相位旋转的改进算法 . 19 3.3 基于自适应相位的改进算法 . 20 3.4 基于改进的自适应相位旋转算法 . 24 3.6 本章小结 . 25 第四章 grover 算法在图像检索中的应用 . 26 4.1 基于纹理特征的图像检索技术 . 26 4.1.1 纹理概述 . 26 4.1.2 基于灰度共生矩阵的特征值提取 . 27 4.1.3 基于灰度-梯度共生矩阵的特征值提取 . 32 南京邮电大学硕士研究生学位论文 目录 iv 4.1.4 基于双树复小波变换的特征值提取 . 36 4.2 图像检索的原型系统 . 38 4.2.1 检索系统框架 . 38 4.2.2 查询方式 . 39 4.2.3 图像的相似性度量 . 41 4.3 基于 grover 算法的图像检索 . 43 4.3.1 基于原始 grover 算法的图像检索仿真与性能分析 . 43 4.3.2 基于 grover 改进算法的图像检索仿真与性能分析 . 45 4.4 本章小结 . 48 第五章 总结 . 49 致 谢 . 50 参考文献 . 51 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪绪 论论 1.1 课题的课题的研究背景研究背景及意义及意义 近年来，量子信息技术的发展向我们展示出了这一新兴领域的独特魅力，它从量子力学 的角度出发研究和解决问题，同时对传统的算法加以改进并取得了较好的效果。 1994年著名数学家shor提出基于量子并行计算的大数质因子分解算法 12， 并证明量子计 算可以攻破目前广泛使用的公钥rsa体系 3。按照经典计算机复杂度理论，分解大数质因子 属于np完全问题，而在shor算法能够以多项式时间求解这类问题，第一次真正显示了量子并 行计算的巨大优势。此后，人们开始积极探索各种np问题的搜索算法。1996年美国科学家 grover提出了一种以量子态并行计算为基础的快速grover量子搜索算法 45， 对于长度为 n的 无序数据库，经典算法只能一个一个地搜寻，直到找到所要的数值为止，这种算法平均地讲 需要寻找2n次，成功概率为1 2，而采用grover搜索算法，则只需要()on次，常规搜索的 复杂度为()o n。1997年，zalka c 6证明了以全0态为起点，不可能存在比grover 量子搜索算 法更快的有效量子算法。 1998年， biham e 7等证明了以非均匀态为起点， 不可能存在比grover 量子搜索算法更快的有效量子算法。1999年，zalka c 8证明了在算法成功率高于50%时，使用 黑盒调用的量子搜索算法中grover搜索算法是最优的。这两个算法的提出证明了量子并行计 算的强大的能力，并引起了量子计算和通信技术的飞速发展。2005年grover提出了固定点量 子搜索 9。2006年，以色列ofer biham等针对初态为 n个量子位的任意纯态的情形，分析了 grover算法，结果发现执行测量的最佳时间与无关，即与有相同数目的标记态数r且 0的最初算法比较，最佳时间是相同的；根据状态的幅度导出了搜索成功的概率，结 果发现这一概率不依赖于r；在将成功概率看成一种纠缠测量的情况下，考察了这些结果的 相关性，并将以前局限于只有一个标记态的grover纠缠测量推广到多个标记态的情况。同年， 清华大学李大法教授等通过将固定点量子搜索中两个等于/3的相位旋转替换为不同的相位 移动，进一步研究了固定点量子搜索算法。同年，江南大学孙力等通过几何法论述了经典 grover算法 10，通过算符法扩展了该算法，并在两种情况下对该算法进行了讨论。在分析算 法实际应用基本策略的基础上，提出了通过量子搜索算法改进经典搜索算法的新思想。2007 年，埃及younes提出了基于固定相位旋转grover算法 11。 近年来伴随着移动多媒体和大型数据库技术的发展，图像检索技术显得越来越有必要进 南京邮电大学硕士研究生学位论文 第一章 绪论 2 行研究，为数字图像检索图像库和视频库正在成为重要的研究课题。本节介绍图像的特征。 多媒体数据的日益增长需求使得图像检索系统需要高效的存储和检索，需要一个快速的方法 来搜索特定类型的图像。目前，大多数的图像检索系统使用颜色、质地、形状、空间关系等 特征来进行匹配。常用的图像检索系统中主要有颜色特征（hsv 空间颜色直方图或 rgb 空间 颜色直方图） 、纹理特征（共生矩阵） 、形状特征（基于阈值优化） 、图像像素的空间关系（马 尔可夫模型）等。颜色特征是最广泛被用来进行图像分割、图像检索、图像增强等，颜色特 征通常不需要考虑空间关系。纹理特征是更有效的描述图像，如砖纹和水纹、自然界动物的 皮肤纹理等。在研究图像检索系统时需要考虑人的视觉特征。然而人类的视觉系统是一个丰 富的系统，视觉信息也寻在人的感性认识。因此图像检索是一个丰富、复杂和有趣的问题。 文字查询 输出结果 传统信息检 索技术 人工标注 图像数据库 图像标注数据库 图1.1 传统的图像检索过程 从图1.1中可以看出，传统的图像方法是通过人工标注图像来进行检索，即基于语义的图 像搜索。但是随着互联网络上图像的日益增加，图像库将会变得越来越庞大，人工标注的工 作量将会很大，并且由于一幅图像包含着丰富的内容。例如一幅摄影图像，不同的人会进行 不同的标注，主观感觉色彩会影响标注的内容，有的人会标注图片中的人物，忽略了图像中 的背景因素，这样将导致图像中的背景内容被忽略。另外一幅图像的内容由于包含着丰富的 信息，用文字不能够准确的表达图像所表达的内容。因此用传统人工标注的方法已经不能够 满足图像搜索的需求。 基于上述原因，基于内容的图像检索方法应用而生。即通过计算机图像处理和分析系统 提取图像中的特征，然后采用一定的方法度量，就能够检索出用户需要的检索结果。这样就 可避免人工标注的主观性和降低了对海量图像进行人工标注的工作量。目前已经有了基于内 容的图像检索（cbir）原型系统。著名的有ibm推出的qbic系统 12，mit实验室开发的 photobook系统， 哥伦比亚大学实验室开发的visualseek系统，但商用的图像检索系统仍未能 实际应用。 基于内容的图像检索系统流程图如图1.2所示: 南京邮电大学硕士研究生学位论文 第一章 绪论 3 图像数据库 待搜索图像 特征值提取特征数据库 特征值提取特征值匹配搜索结果 特征值预先提取阶段 图像搜索阶段 图1.2 基于内容的图像检索系统流程图 工作过程分为两个阶段：对图像库特征值的预先提取阶段和图像搜索阶段。在图像库特 征值的预先提取阶段，计算出图像库中的所有图像所对应的特征值，并将特征值存储在数据 库中。在图像搜索阶段，计算需要搜索图像的特征值，并将其与数据库中的特征值进行匹配， 并按照一定的度量标准输出需要检索的图像。 1.2 本论文的主要研究本论文的主要研究内容内容 本论文研究量子 grover 搜索算法的改进算法，并改进后的算法应用于基于纹理的图像检 索系统中。通过量子并行计算的特性使得改进后的 grover 算法不仅具有快递搜索速度，也提 高了搜索的成功率。改进后的 grover 算法不在数据库搜索中有很好的性能。最后将其运用于 图像检索中，并实现了图像检索系统，利用图像的纹理特性进行了图像检索的实验。 本论文结构安排及主要内容如下： 第二章：研究了量子计算的特性，包括量子态、量子逻辑门和量子并行性。在此基础上， 研究了 grover 量子搜索算法的原理，模拟实验了 grover 算法，并分析了 grover 量子搜索算 法的缺陷。 第三章：研究了三种 grover 算法的改进算法，并设计了一种改进的 grover 算法。 第四章： 研究了纹理特征、 纹理特征的提取方法、 图像检索的原型系统， 并将改进的 grover 算法用于图像检索，最后进行了仿真实验和性能分析。 第五章：对论文工作进行简单总结。 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 4 第二章第二章 grovergrover 量子搜索算法量子搜索算法 信息是客观事物状态或运动特征的表征。例如，早期的计算机是利用纸带穿孔卡片来表 示“有”（“1”）和“无”（“0”）的两种状态。随着电子技术的发展，用半导体管的逻 辑元件来表示开、关的两种状态。1932 年诺贝尔物理学奖获得者德国莱比锡(leipzig)大学 的海森伯（werner heisenberg，1901-1976）创立了量子力学，揭开了物理学微观粒子研究的 新篇章。量子的概念在微观粒子世界里通常包括原子、电子和中子等。在量子力学中，量子 信息(quantum information)是关于量子系统“状态”所带有的物理信息。 通过量子系统的各种 相干特性(如量子并行、量子纠缠和量子不可克隆等)，进行计算、编码和信息传输的全新信 息方式。例如，光子的两种不同极化；在均匀电磁场中核自旋的取向；图 2.1 所示的围绕单 个原子旋转的电子的两种状态等都可表示量子信息。 10 图 2.1 用原子中电子的两种自旋状态表示的量子比特 在量子信息理论中，量子比特是基本存储单元。利用二维复数空间的一个向量来表示一 个量子，它的两个极化和经典信息的二进制存储单元状态的“0”和“1”对应。量子比特区 别于经典比特在于，量子比特可以是“0”和“1”量子状态的叠加态。 下面介绍量子计算基本原理，并引出 grover 算法及其改进算法。 2.1 量子信息论基础量子信息论基础 2.1.1 量子计算基础 1. 单量子比特 经典计算机中的信息是由 0 和 1 二进制来表示。在量子计算中，是用量子比特的概念来 计算的，规定采用0和1表示微观粒子的两种状态。可以由这两个基本状态的线性组合来表 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 5 示单量子比特的任意状态。称“”为狄拉克(dirac)记号，它在量子力学中表示状态，经典 比特和量子比特的区别在于量子比特还可以是状态0和1的线性组合，称为叠加态 (superposition)，即 01 （2-1-1） 上式 2-1-1 中和是复数，表示量子态的概率幅，即经测量后量子态坍缩到0的概 率为 2 ，坍缩到1的概率为 2 ，和满足关系式 22 1 (2-1-2) 因此，量子态也可由概率幅表示为, t 。显然，在式 2-1-1 中，当1,0时, 即为基本状态0，此时可表示为1,0 t ；相反，当0，1时，即为基本状态1，此时 可表示为1,0 t 。下面以电子为例来解释叠加态。一个电子可以处于低能级的基态0，也可以 处于高能级的激发态1，叠加原理告诉我们，电子可以处于这两种状态的线性组合态，即叠 加态01，如图 2.2 所示 叠加 基态 激发态 叠加态 0 1 01 图 2.2 电子基态0、电子激发态1构成叠加态示意图 电子处于叠加态01时，那么对叠加态测量就扰乱了系统，并导致叠加态坍缩到基 态或激发态的一个特定的状态。如图 2.3 所示，电子以概率 2 选择状态0，而以概率 2 选 择状态1 14。 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 6 测量 叠加态 以概率选择状态 以概率选择状态 01 2 0 2 1 图 2.3 叠加态01经过测量后坍缩为基态和激发态的示意图 式 2-1-1 可改写为 cos0sin1 22 i e （2-1-3） 式 2-1-3 中cos 2 、sin 2 i e 均为复数， 2 cos 2 为量子位于0的概率， 2 sin 2 i e 为量子位于1 的概率， 2 cos 2 和 2 sin 2 i e 要求满足条件式 2-1-4 22 cossin1 22 i e （2-1-4） cos 2 和sin 2 i e 分别表示位于状态0和1的概率幅。用 bloch 球面表示如图 2.4，球面上 的一点p可由和定义。 x y z p 0 1 图 2.4 bloch 球面 该图表示的是单量子比特，多量子比特的叠加态不能够在图上直观地表示 1314。 2. 双量子比特 两个经典比特有四种状态：00，01，10和11。两个量子比特组成：00，01，10和11 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 7 的基态。两个量子比特的叠加态为 00011011 00011011aaaa （2-1-5） 测量坍缩后00，01，10，11的概率是 2 00 a， 2 01 a， 2 10 a， 2 11 a，上述概率之和为1的 归一化条件为 2 2 0,1 1 x x a （2-1-6） 对于第1个状态的量子比特，测量得到0的概率是 22 0001 aa，状态转变为 0001 22 0001 0001aa aa （2-1-7） 测量为1的概率 22 1011 aa，状态转变为 1011 22 1011 0011aa aa （2-1-8） 对于第2个状态的量子比特，测量为0的概率是 22 0010 aa，状态转变为 0010 22 0010 0010aa aa （2-1-9） 测量得到1的概率为 22 0111 aa，状态转变为 0111 22 0111 0111aa aa （2-1-10） 3. 多量子比特 类似于单量子比特，n量子比特也可以处于2n个基本状态的叠加之中，即 0,1 n x x ax （2-1-11） 状态x的概率幅为 x a且满足 2 2 0,1 1 x x a （2-1-12） 例如，当3n 时 000001010011 000001010011aaaa 100101110111 100101110111aaaa 其中概率幅满足 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 8 22222222 000001010011100101110111 1aaaaaaaa 2.1.2 量子逻辑门 1. 单比特量子门 在量子计算方法中，改变量子位的状态需要进行酉变换。单比特的量子门由2*2的矩阵 表示，规定量子门的矩阵u必须是酉的，用公式表示为u ui ，u 为u 的共轭转置。下表 2.1 列出了 7 个经常遇到的单比特量子门 1516、符号和矩阵。 表 2.1 常用单比特量子们的名称、符号及酉矩阵 名称符号矩阵表示 hadamard门 x 门 y 门 z 门 相位门 量子旋转门 门/8 h x y z s t r 11 1 112 01 10 0 0 i i 10 01 10 0i /4 10 0 i e cossin sincos 由表 2.1 可知，()/2hxz和 2 st。 需指出，t门成为/8门， 但是表中矩阵的是/4， 是由于 /8 /8 /4 /8 100 00 i i i i e te ee 故称为/8门。 量子旋转门的推导公式如下： cossincoscos() sincossinsin() r （2-1-13） 2. 多比特量子门 受控非门的线路图及矩阵表示如图 2.5 所示 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 9 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 cn u 控制量 子比特 目标量 子比特 a b a ba 图2.5 两位受控非门及矩阵表示 该量子门用量子态表示为0000，0101，1011，1110。用酉矩阵 cn u来描 述。例如，输入状态为00，输入的目标量子比特为0b ，输入的控制量子比特为0a ， 对应的基本状态向量用矩阵形式表示为1000 t ，酉矩阵 cn u的变换过程可表示为 100011 010000 000100 001000 可以看出，状态00通过 cn u作用后的状态仍为00。当输入状态为01、10和11时的作 用过程可表示为 100000100000100000 010011010000010000 , 000100000110000101 001000001001001010 从上述变换可以看出， 酉矩阵 cn u具有使受控非门变换的功能， 用量子态表示为0000， 0101，1011，1110。在这里受控非门看成为异或门的延伸，受控非门的作用量 子态可表示为,a ba ba，表示模2加，这等同于异或运算。 现在介绍三比特量子门，常见的有 toffoli 门，即有三比特的输入和输出，toffoli 门实际 上是受控非门的延伸，如图 2.6 所示。 a b c a b cab 图 2.6 toffoli 门线路表示 输入a，b为控制量子比特，c为输入目标比特，其中输入a，b状态经过 toffoli 门后的 状态不进行改变，而输入c的量子比特在a与b都为1时，输入的目标量子比特c将会变为 cab，其他三种情况不变化。一般情况下，在有nk个量子比特时，u成为k个量子比特 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 10 的酉算子，受控非门的计算这是定义为 1 2. 1212 ( ). n x xxn nn c ux xxx xxu (2-1-14) 上式中u的指数 12.n x xx是比特 12 ,. n x xx的乘积，只有前n个比特都为1时，u算子才会 计算后k个量子比特，下图为( ) n c u运算线路表示。 u 5n 3k 图 2.7 ( ) n c u运算线路表示 2.1.3 量子并行性 量子并行计算的优点在于可以在同一个量子线路中完成，而经典的并行是多重电路同时 进行。 设( ): 0,10,1f x是具有一个比特的定义域和值域的函数。在量子计算机上，经过一定 的逻辑门将量子计算机中初态为, x y的两个量子比特序列转化为,( )x yf x,其中表示模2 加法。一般定义量子比特的寄存器为量子寄存器。下图中的两个寄存器x为数据寄存器 ( )yf x为目标寄存器。图所示，将,( )x yx yf x称为 f u,经证明 f u满足酉的。0y 时， 第二个量子比特的状态变为( )f x。 01 2 0 x y x ( )yf x f u 图 2.8 同时计算(0)f和(1)f的线路图 根据上述图 2.8 的线路表示，把 f u加到基本计算基外的输入，比如叠加态 01 2 ,这个叠 加态由hadamard门作用于0实现，应用 f u得到的最终状态为： 0,(0)1,(1) 2 ff (2-1-15) 南京邮电大学硕士研究生学位论文 第二章 grover 量子搜索算法 11 分析上述式子，看起来似乎同时对x的两个值计算了( )f x。不同于经典计算机，通过多重 电路来计算多个( )f x。量子计算机通过不同量子状态的叠加特性,通过计算单个( )f x就可同时 算出多个x的值。已知 f u是一个线性变换，如果将 f u作用于某个叠加态，它将会同时作用于 该叠加态的所有基向量，并且把对所有基向量的作用结果进行叠加，从而产生一个新的叠加 态。可见，由此方法计算函数( )f x，只需应用一次 f u就可同时计算出x取n个不同值时的函 数值。量子算法的强大能力正是来源于量子并行性。 2.2 grover 量子量子算法算法 1996 年 grover 提出了开创性的 grover 算法 17。 1997 年 grover 提出了应用量子计算能将 对无序数据库的搜索问题进行二次加速作用，实现了将经典算法的搜索步数从n缩小到n。 并且这种搜索算法随着数据库规模的增大会显著提高搜索效率20。 2.2.1 基于黑箱的搜索思想 在考虑含有2nn 个数据库的搜索问题，其中搜索的解恰好有m个。将数据库中的每个 元素进行量化后，存储在n个量子比特中，m与n满足关系式(1)mn。将搜索问题表示成 从0到1n 的整数x，其中函数f定义为，如果x是需要搜索的解，( )1f x ,若不是需要搜索 的解，那么( )0f x 。 假设有一个黑箱，其中的一个比特用来识