集合运算在量子计算机上的实现

论文摘要

量子计算与量子信息是涉及物理学、计算机科学、数学以及信息科学等多个学科的新兴综合性交叉研究领域。在处理众多特殊问题上,量子计算机展示了它比传统计算机,更加优越的巨大潜力。例如：1994年,petershor提出的算法能在量子计算机上有效的解决两个非常重要的问题：整数质因数分解、离散对数问题,这些问题在传统计算机上都是不能有效的被解决的。在量子计算的研究中,计算性能的优越性主要体现在算法的有效性上。目前为止,被公认的最具代表性的量子算法有Shor的大数质因子分解算法以及Grover提出的数据库搜索量子算法。然而,Grover搜索算法在搜索复杂的数据库时存在着很大的足限性,因为Grover搜索算法只能处理在全空间中的量子比特,而不能处理在子空间中的量子比特。例如,它在处理部分量子比特时不可能保持另一部分量子比特不变。此外,数据在被处理之前,必须先加载到寄存器中,才能完成处理任务。但由于经典的数据是通过输入输出设备,被逐个的加载到寄存器中去的。输入输出设备由于其逐个加载数据的方式,严重地拖慢了计算机的运算速度,从而成为经典计算机的效率瓶颈。量子计算机又不能直接处理经典的数据信息,只能对量子态进行处理。要对量子态进行处理必须把经典数据加载到量子态上,因此必须有一个针对量子计算机的数据存储方案。这正是本文将研究的量子数据加载方案(QLS)。数据库操作、信号处理、图像压缩等领域,由于其数据库的庞大性,在经典计算机上处理这类问题是非常困难的。而这些问题最终又可以归结为对集合的操作。因此在量子计算机上有效地处理集合问题,就成了解决上述问题的关键。基于以上问题,在这篇文章中,提出了基于量子装载方案(QLS)和旋转子空间理论的量子集合算法,能够在量子计算机上有效地解决集合运算类问题。本文分为以下三个部分：第一部分对量子计算的历史概况进行了简述,以及量子计算的准备知识。对历史上比较重要的量子算法进行了重点分析,如shor因子分解算法、Grover搜索算法等已被提出的算法。第二部分这部分介绍了旋转子空间理论和量子数据加载方案(QLS),同时也介绍了针对Grover量子搜索算法而提出来的Ggeneral,最后在这些算法的基础上提出了一个新量子集合算法。第三部分在文章最后对量子集合算法的一个运用——模式识别进行了分析。主要是从如何实现在包含大量的干扰信号中实时地识别出真实的目标这方面进行了详细的分析。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 量子计算的历史概况
• 1.2 本文致力研究的关键性问题,以及需达到的目标
• 1.3 本课题研究的意义以及研究所采用的方法
• 1.4 本章小结
• 第二章 量子计算的基本原理和基础概念
• 2.1 量子比特
• 2.2 量子比特门
• 2.3 量子并行性及量子叠加原理
• 2.4 量子态随时间的演化
• 2.5 量子纠缠与量子测量
• 2.6 本章小结
• 第三章 量子算法
• 3.1 "black box”指数加速的量子算法
• 3.1.1 Deutsch算法
• 3.1.2 Deutsch-jozsa算法
• 3.2 量子Fourier变换
• 3.3 Shor大数因子分解算法
• 3.4 量子求阶算法
• 3.5 量子Fourier变换的一些应用
• 3.6 Grover量子搜索算法
• 3.7 本章小结
• 第四章 量子数据装载方案（QLS）和旋转子空间理论
• 4.1 量子数据装载方案（QLS）
• 4.2 旋转子空间理论
• 4.3 本章小结
• 第五章 量子集合算法
• 5.1 集合求交集算法概述
• 5.2 构建幺正操作
• 5.3 量子集合算法的实现
• 5.4 量子集合算法的运算性能分析
• 5.5 本章小结
• 第六章 量子集合运算的应用
• 6.1 多模式识别概述
• 6.2 量子多模式识别
• 6.2.1 数据结构和幺正变换
• 6.2.2 多模式识别量子算法的实现
• 6.3 本章小结
• 第七章 结论
• 参考文献
• 致谢