Grover量子搜索算法的改进及其在图像检索中的应用硕士论文.pdf

单位代码: 10293 密级: 公开





硕士学位论文

论文题目: Grover 量子搜索算法
的改进及其在图像检索中的应用


学号 Y001090442
姓名张海雄
导师李飞教授
学科专业信号与信息处理
研究方向量子信息技术
申请学位类别工学硕士
论文提交日期二〇一二年六月
南京邮电大学学位论文原创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得
的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包
含其他人已经发表或撰写过的研究成果,也不包含为获得南京邮电大学或其它
教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的
任何贡献均已在论文中作了明确的说明并表示了谢意。
本人学位论文及涉及相关资料若有不实,愿意承担一切相关的法律责任。



研究生签名:_____________ 日期:____________


南京邮电大学学位论文使用授权声明
本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文
档;允许论文被查阅和借阅;可以将学位论文的全部或部分内容编入有关数据库进行检索;
可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质
论文的内容相一致。论文的公布(包括刊登)授权南京邮电大学研究生院(筹)办理。
涉密学位论文在解密后适用本授权书。


研究生签名:____________ 导师签名:____________ 日期:_____________
南京邮电大学
硕士学位论文摘要



学科、专业:工学信号与信息处理
研究方向: 量子信息技术

作者:2009 级研究生张海雄
指导教师:李飞教授

题目:Grover 量子搜索算法的改进及其在图像检索中的应用
英文题目:Improvement of Grover Quantum Search Algorithm and Its
Application to Image Retrieval



主题词:量子计算;Grover 算法;图像检索;特征提取

Keywords: putation; Grover Algorithm; Image Retrieval;
Feature Extraction
南京邮电大学硕士研究生学位论文摘要
摘要
以量子并行计算为基础的Grover量子搜索算法,对于长度为 N 的无序数据库搜索,计算复
杂度仅为 ON()。
Grover 量子搜索算法在进行搜索时,随着搜索目标数的增加获得正确结果的概率大幅度
下降,并且当搜索的目标数占数据总数的一半时,无论搜索多少次,所得的概率都为1/ 2 ,此
时算法是无效的。本文研究了 Grover 量子搜索算法及其改进,并将其应用于图像检索。主要
的研究工作有:
首先,研究了 Grover 量子搜索算法,并在经典计算机上模拟实现了量子 Grover 算法。
分析了原始 Grover 算法存在的缺点,研究了已有三种改进的 Grover 算法,在此基础上设计
了一种改进的自适应相位旋转的 Grover 量子搜索算法。
其次,研究了基于纹理特征的图像检索,用基于灰度共生矩阵、灰度-梯度共生矩阵和双
树复小波变换的三种方法分别对图像的纹理特征进行了提取。
最后,将改进后的 Grover 量子搜索算法用于图像检索。仿真结果表明,该算法在图像检
索中能得到较好的检索效果。


关键词:量子计算;Grover 算法;图像检索;特征提取
I
南京邮电大学硕士研究生学位论文 ABSTRACT
ABSTRACT
To search a unordered database with a length of N using Grover algorithm, which is based on
the quantum state of putation, plexity 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,