论文部分内容阅读
随着量子计算机的实现和发展,基于量子计算机运行的量子算法也越来越丰富,其中最重要的一部分是量子搜索算法,量子搜索算法已被证实对相应的经典算法有指数倍的加速效果。但是,量子计算机用于计算的量子比特数目始终存在限制,当需要处理的大数据集包含的比特数超过了量子处理器能处理的最大数据量时,便不能直接在整个搜索空间中找到搜索问题的解,为了解决这一问题,本文将做以下具体研究:1、通过对量子处理器和量子计算的研究,发现了量子处理器在量子搜索问题的应用方面存在一定的自身局限性,一方面是由于量子纠缠态难以控制,所以量子处理器包含的量子比特数目始终有限,因此量子搜索算法的实际应用中,必须要考虑用有限比特解决大数据集的搜索问题。另一方面,由于量子系统存在退相干性,所以在设计量子搜索算法的时候需要考虑如何减少计算步骤和计算时间来确保系统的稳定性和高准确率。2、从需要解决的搜索问题入手,设计了基于Grover算法的分块搜索的量子算法。进一步,通过对分块的量子搜索算法进行分析证明得出,对每块数据适当进行不完全Grover运算可以得到更优化的搜索方案,且最优方案出现在迭代次数随着数据块位置靠后会越来越大的情况下,据此提出了一个优化分块搜索算法。最后在Matlab环境中进行优化求解并仿真,仿真的结果表明该优化后的分块搜索算法可以达到最高6%左右的优化率,从实验方面证实了该优化分块搜索算法的可行性。3、设计量子线路。考虑到Grover算法在优化分块搜索算法上的应用,将该算法分模块分析,由子模块的算子功能推导出该模块中酉算子的矩阵形式,再由酉算子的矩阵形式选择合适的量子门组成量子线路来实现子模块的功能。接着将子模块的量子线路结合起来实现一个Grover迭代的功能,最后根据优化分块搜索算法的迭代次数调用迭代模块的量子线路来完成搜索。4、将量子线路代码化,使用Python中的QISIKT库连接IBM Q的接口,实现优化分块搜索算法在IBM Q的量子云平台上成功运行。记录优化分块搜索的程序运行时间并与完整Grover搜索进行对比,之后分别利用优化分块搜索算法的代码运行时间和算法迭代次数来计算优化率并分析算法的性能,通过对优化率的对比发现二者趋势相同,表明结果符合理论预期。