离散量子行走搜索算法的研究

《离散量子行走搜索算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、：誇参參密级：Ｌ＿＿Ｍ一—一ＵＤＣ．一：００４４？广．争学号：祕詞用师＂．－鱗急！£杂，婆嫌硕±学位论文离散量子行走搜索算法的研究研究生姓名：童彬彬导师姓名：陈汉武申请学仿类别工学硕±学位授予单位东南大学一２０纯学科名称计？化科学与技术论义答辩日期１６年６月３日二级学科名称学仿授予日期２０１６年月日答辩蚕员会丰席来方巧评阅人２０１６年６Ｗ３ｎ乘朵／扛參硕±学位论文离散量子行走搜索算法的研究专业名称：计算机科学与

2、技术研究生姓名：章彬彬导师姓名：陈汉武ＲＥＳＥＡＲＣＨＯＮＤＩＳＣＲＥＴＥＵＡＮＴＵＭＱＲＡＮＤＯＭＷＡＬＫＳＥＡＲＣＨＡＬＧＯＲＩＴＨＭＡＤｉｓ化ｒｔａｔｉｏｎＳｕｂｍｉｔｅｄ化ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙＦｏｒｔｈｅＡｃａｄｅｍｉｃＤｅｇｒｅｅｏｆＭａｓｔｅｒｏｆＥｎｇｉｎｅｅｒｉｎｇＢＹＺＨＡＮＧＢｉｎｂｉｎＳｕｅｒｖｉｓｅｄｂｐｙＰｒｏＥＮＨａｎｗｕ伤ｓｓｏｒＣＨＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉ

3、ｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙＪｕｎｅ２０１６东南大学学位论文独创性汚明本人声明所呈交的学位论文是我个人在导师指导下进行的研巧工作及取得的研究成果。尽我所知，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含其他人己经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料一。与我同工作的同志对本研巧所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名；专棘碼日期；Ｗｌｂ＇ｂ．ｂ东南大学学位论文使

4、用授权污明东南大学、中国科学技术信息研巧所、国家图书馆有权保留本人所送交学位论文的复印件和电宁文档，可！＾＾采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致，允许论文被査阅和借阅，可Ｗ公布（包括Ｗ电子信息形式刊登）。除在保密期内的保密论文外论文的全部内容或中、英文摘要等部分内容。论文的公布（包括Ｗ电子信息形式刊登）授权东南大学研巧生院办理。研巧生签名！导师签名；作？摘要１９９３年，Ａｈａｒｏｎｏｖ提出了量子随机行走的概念，相比于经典随机行走，量子随机

5、一行走具有更快的扩散速度。２０的年，第个量子随机行走搜索算法，即ＳＫＷ算法，从理论上证实了量子随机行走相对于经典算法的优越性，并探索了量子随机行走算法新的应用领域，。近年来若干研巧者致力于量子随机行走的行走结构和算法的研究。本文提出使用散射量子行走搜索完全图上的结构异常。如果在Ｗ个顶点的完全图中一个悬挂点，加入，这将破坏完全图的对務性。算法首先给出了行走酉算子的定义利用，完全图的对称性，将行走空间巧缩到低维不变子空间并确定了酉算子在该子空间中作，用的形式。为了分析算法演化过程利用微扰理论求解算子的特征

6、值和特征向量，将算法初态用特征向量表示，Ｗ此，并计算行走后的终态分析算法的时间复杂度和成功概率。算法分析及Ｍａｔｌａｂ仿真结果均表明，利用散射量子行走可在步内接近于１〇的概率找到异常位置，而经典算法中使用邻接矩阵查找该异常的时间复杂度为（Ａ〇。因此散射量子行走捜索算法可Ｗ实现二次加速。关键词：离散量子行走，完全图，结构异常ＩＡｂｓｔｒａｃｔＡｂｓｔｒａｃｔＱｕａｎｔｕｍｒａｎｄｏｍｗａＵｃｉｓｐｕｔｆｏｒｗａｒｄｂｙＡｈａｒｏｎｏｖｉｎ１９９３．Ｃｏｍｐａｒｅｄｗｉｔｈ

7、化ｅｃｌａｓｓｉｃａｌｒａｎｄｏｍｗａｌｋｕａｎｔｕｍｒａｎｄｏｍｗａｌｋｈａｓａｆａｓｔｅｒｄｉｆｆｕｓｉｏｎｖｅｌｏｃｉｔ．Ｉｎ２００３化ｅｆｋｓｔ，ｑｙ，ｕａｎｔｕｍｒａｎｄｏｍｗａｌｋｓｅａｒｃｈａｌｇｏｒｉｔｈｍｎａｍｅｌｔｈｅＳＫＷａｌｏｒｉｔｈｍｔｈｅｏｒｅｔｉｃａｌｌｒｏｖｅｄｔｈｅｑ，ｙｇｙｐ，ｓｕｅｒｏｒｔｏｆｕａｎｔｕｍｒａｎｄｏｍｗａ化ｃｏｍａｒｅｄｗｉｔｈｔｈｅｃｌａｓｓｉｃａｌｏｒｉｔｈｍｓａｎｄｘｏｒｅｄｔｈｅｐｉ

8、ｉｙｇ，ｅｐｌｑｐ＊ｎｅｗａｌｉ知ｔｉｏ打ｆｉｅｌｄｓｏｆｕａ打ｔｕｒｎｒａｎｄｏｍｗａｌｋａｌｏｒｉｔｈｍ．ＩｎＫｃｅｎｔｅａｒｓｓｏｍｅｒｅｓｅａｒｃｈｅｉ：ｓ，ｐｐｑｇｙｈａｖｅｄｅｖｏｔｅｄ化ｔｈｅｒｅ化ａｒｃｈｏｆｗａｌｋｉｎｇｓ