学位论文 > 优秀研究生学位论文题录展示

绝热量子搜索算法研究

作　者: 张映玉
导　师: 卢正鼎；胡和平
学　校: 华中科技大学
专　业: 计算机应用技术
关键词: 绝热演化 量子计算 量子搜索 Grover算法 量子线路模型
分类号: TP301.6
类　型: 博士论文
年　份: 2011年
下　载: 72次
引　用: 0次
阅　读: 论文下载
 

内容摘要


Shor大整数因子分解算法、Grover算法等量子算法已经证明了量子计算具有比经典计算更强大的计算能力。然而,设计快速的量子算法是困难的,主要有两方而的原因。一方而,算法设计者的直觉杭根于经典世界之中,算法设计者必须设法避开直觉的干扰才能设计出优越的量子算法。另一方面,设计者所设计的量子算法必须超出所有的经典算法,否则很难引起广泛兴趣。绝热量子计算是继基于量子快速傅里叶变换量子算法研究及Grover算法研究之后的另一量子算法研究领域。它以量子绝热定理为理论基础,具有与生俱来的抵抗量子噪声的能力,本质上属于连续时间量子计算,不同于基于离散幺正变换序列的量子计算模型—量子线路模型。无序数据库搜索问题是量子搜索算法包括Grover算法研究的核心问题,也是量子计算研究的热点问题。利用绝热量子模型研究、解决该问题有助于理解绝热量子计算乃至量子计算的本质,具有重要的理论意义。从表而来看,全局绝热量子计算模型采用线性由线性插值法给定,它的时间复杂度制约公式是由绝热条件作用于整个时间区间而得到；局部绝热量子计算模型的绝热路径及时间复杂度制约公式由绝热条件作用于无穷小的时间区间而得到；部分绝热量子计算模型也采用线性插值法给出系统哈密顿量,但其只在使系统基态和第一激发态之间的能隙最小的时间点附近执行绝热演化。然而,对绝热量子算法的研究发现,全局、局部以及部分绝热量子算法本质区别在于演化路径的不同。绝热量子系统的核心要素是系统哈密顿量。给定了系统哈密顿量,就给定了整个量子系统的演化过程。在绝热量子计算中,给定初始哈密顿量、末态哈密顿量以及路径参数就给定了系统哈密顿量。绝热量子计算的核心问题是系统基态和第一激发态之间的最小能隙问题。一般情况下,系统哈密顿量的能谱及该最小能隙是难以求解的。但在特殊情况下,可以采用降维的方法,把系统工作的N(一般设为N=2n)维希尔伯特空间降至相对较小的维数,再采用近似或解析的方法求解系统基态和第一激发态之间的最小能隙。例如,把Grover问题看做SAT问题的特例,可以把N维降为n+1维,再采用近似方法求解系统基态和第一激发态之间的最小能隙。已有研究表明Grover算法是基于Oracle调用的最优量子算法,其时间复杂度为O(√N)；全局绝热量子搜索算法只能得到和经典暴力搜索一样的时间复杂度；局部绝热量子搜索算法具有和Grover算法一样的时间复杂度；部分绝热量子算法在匹配搜索条件的数据库条目数M=1的情况下,具有和Grover算法一样的时间复杂度,但在M>1的情况下,其时间复杂度要快O(√M)。对Grover算法和局部绝热量子搜索算法的最优性证明目前权限于M=1(M为标识态的数目)的情况。通过修改不同末态之间的度量,利用绝热条件可以证明局部绝热量子搜索算法在M>1的情况下也是最优的,即不存在其他绝热演化路径,得到更优的绝热量子搜索算法。值得提的是,该证明并不包含部分绝热量子搜索算法。绝热量子计算本质上是连续时间量子计算,把它转化为量子线路模型一般遵守两步法则：第一步,对量子算法的运行时间进行分片,在每一个小的时间片内,用一个幺正变换近似该时间片内的连续时间量子操作；第二步,分析由近似所引入的误差,并最终决定分片数。

全文目录


摘要  4-6
Abstract  6-8
目录  8-10
1 绪论  10-24
  1.1 理论背景  10-13
  1.2 量子搜索算法现状与分析  13-21
  1.3 项目背景与研究内容  21-22
  1.4 论文组织结构  22-24
2 量子计算  24-36
  2.1 量子比特及量子并行性  24-28
  2.2 离散时间量子算法  28-33
  2.3 连续时间量子算法  33-35
  2.4 本章小结  35-36
3 绝热量子算法及其分析法  36-59
  3.1 绝热量子算法及其时间复杂度  36-40
  3.2 3SAT问题的绝热量子算法  40-45
  3.3 一般化绝热量子搜索算法及其应用  45-57
  3.4 本章小结  57-59
4 部分绝热量子搜索算法  59-68
  4.1 末态哈密顿量为投影算子的绝热系统  59-64
  4.2 部分绝热搜索算法及时间复杂度  64-66
  4.3 本章小结  66-68
5 量子搜索算法的最优性证明  68-76
  5.1 基本Grover算法的最优性证明  68-70
  5.2 局部绝热搜索算法的最优性证明  70-74
  5.3 本章小结  74-76
6 绝热量子搜索算法的线路模型  76-85
  6.1 全局绝热量子搜索算法的线路模型  76-80
  6.2 局部绝热量子搜索算法的线路模型  80-82
  6.3 部分绝热量子搜索算法的线路模型  82-84
  6.4 本章小结  84-85
7 总结与展望  85-87
  7.1 论文总结  85-86
  7.2 工作展望  86-87
致谢  87-88
参考文献  88-93
附录1 攻读学位期间发表的学术论文  93-94
附录2 基本量子门及其线路符号  94-96
附录3 绝热条件相关证明与推导  96-99
  3.1 经典量子化条件的来源  96
  3.2 绝热定理充分条件的推导  96-98
  3.3 量子化条件的必要性证明  98-99

相似论文

  1. 基于量子搜索的Ad Hoc网络路由协议研究,TN929.5
  2. 量子粒子群算法研究及其在图像矢量量化码书设计中的应用,TP301.6
  3. 量子遗传算法在机械优化问题中的应用研究,TP18
  4. 具有高概率的量子计算算法研究,TN918.1
  5. 自旋链中任意两粒子纯态的传输,O413
  6. 量子有限自动机等价性判定研究,O413
  7. 绝热量子搜寻算法和Deutsch-Jozsa算法的物理实现研究,O431.2
  8. 量子进化算法及其在QoS组播路由和网络入侵检测中的应用,TP393.08
  9. 基于量子点的分布式量子计算,TP38
  10. 量子绝热过程及其与宏观可逆过程的对比研究,O431.2
  11. 通过腔Input-Output过程制备Cluster态及其相关应用,O431.2
  12. 量子进化算法的研究及应用,TP301.6
  13. 基于Josephson结实现受控U门的研究,O413.1
  14. 基于量子计算技术的智能算法的研究与应用,TP301.6
  15. 量子进化算法及其应用研究,TP18
  16. 量子群智能算法及其在控制器优化设计中的应用,TP18
  17. 基于粒子群优化的遥感图像聚类研究,TP751
  18. 原子—分子BEC统计特性的研究,O431.2
  19. 基于光子不可区分度测量单光子超短脉冲的研究,TN241
  20. 量子搜索算法研究及量子纠缠计算,TP391.3
  21. 量子遗传算法的改进研究及在路由选择问题中的应用,TP18

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com