基于离散时间量子行走模型的搜索算法研究

摘要

作为设计随机算法的一个有力的数学工具，经典随机行走为因式分解、k-SAT、图同构等问题提供了一系列最广为人知的算法。量子行走提供了加速经典随机行走的可能性，近年来设计基于量子行走的搜索算法成为量子计算领域的研究热点。研究的核心问题之一是搜索算法在何种图结构上的行走能实现量子加速。算法的分析是其中的难点，量子迭代算法分析的关键是求得演化算子的特征谱，从而确定算法的演化过程。早期成功的搜索算法普遍采用Grover算子作为算法的演化算子，当图满足某种性质时，如正则性、对称性，将算法的演化空间限定在坍缩图对应的子空间中加以分析。抽象搜索算法和算子扰动理论是基于离散时间量子行走搜索算法的两种主要分析手段。本文在以下方面做出了探索:
　　(1)搜索算法在商图上的演化算子的计算是搜索算法分析的一个重要步骤。演化算子包含移位算子和硬币算子。以超立方体为例，构造出Grover硬币算子在商图上对应的矩阵形式，并给出了其正确性证明。由于商图上的移位算子可由原图上的移位算子直接导出，从而确定了使用Grover算子作为硬币的量子行走在商图上的演化算子。超立方体商图上的硬币算子形式可以推广至其他图上，如完全图、强正则图等。
　　(2)图上结构发生改变称之为结构异常。完全图有外接图称之为外部结构异常;内部结构发生改变成为内部结构异常。基于散射量子行走设计搜索算法定位完全图上的结构异常。利用完全图的对称性，将算法的搜索空间限定在一个低维的坍缩图空间。利用算子扰动理论证明只要完全图和外接图的连接度足够小，则完全图外接任意图均可以在O（√N）时间步内解决。用类似的方法证明完全图缺失边和有多余自环边时搜索算法也有二次加速。
　　(3)基于散射量子行走设计强正则图上的搜索算法研究图的对称性对搜索算法性能的影响。对于较大的N强正则图不具有全局对称性，但可以利用局部对称性将搜索空间限制在对应坍缩图的低维子空间中。当k与N同阶时，利用Cottrell提出的基本配对定理量化算法的性能;当k与√N同阶时不满足该定理，使用算子扰动理论分析。结果表明，在两类强正则图上的搜索算法均可在O(√N)时间步内以接近1的概率定位到目标顶点。
　　(4)完全图上结构异常搜索和强正则图上搜索的成功说明图的正则性和全局对称性不是最优搜索的必要条件。二者的分析过程表明星图上的基本配对定理可以推广至完全图及部分强正则图的坍缩图上。

目录

声明

摘要

符号表

第一章 概述

1．1．1 量子力学基本假设

1．1．2 基本量子门

1．2 量子行走

1．2．1 离散时间量子行走

1．2．2 1D Hadamard行走示例

1．2．3 连续时间量子行走

1．3 论文组织

第二章 量子搜索算法

2．1 研究现状

2．1．1 基于DTQW的搜索算法

2．1．2 基于CTQW的搜索算法

2．2 搜索算法模型

2．2．1 基于oracle的算法模型

2．2．2 Grover算法

2．2．3 抽象搜索算法

2．3 抽象搜索算法实例

2．3．1 二维空间搜索

2．3．2 SKW算法

2．3．3 元素独立性算法

2．4 算子扰动理论

2．4．1 SQW算法分析

2．4．2 基本配对定理

2．4．3 简并扰动理论

2．5 本章小结

第三章 商图上的Grover硬币算子

3．1 基本概念

3．2 n维超立方体商图上的酉算子

3．3 量子算法中的对称性

3．4 本章小结

第四章 完全图结构异常搜索算法

4．1 基本概念

4．2 外部结构异常举例

4．2．1 完全图外接点

4．2．2 完全图外接三角形

4．3 搜索外部结构异常的一般结论

4．4 内部结构异常

4．4．1 完全图带自环边

4．4．2 完全图有边的缺失

4．5 本章小结

第五章 强正则图上的搜索算法

5．1 预备知识

5．2 搜索算法分析

5．2．1 SRG的坍缩图

5．2．2 算法性能量化

5．3 仿真结果及讨论

5．3．1 仿真结果

5．3．2 量子搜索与图同构

5．4 本章小结

第六章 总结与展望

6．1 量子行走搜索算法

6．1．1 工作总结

6．1．2 搜索算法思考

6．2 量子行走模型

6．3 量子计算面临的挑战

致谢

参考文献

攻读博士学位期间发表论文

攻读博士学位期间参与的科研项目