基于绝热演化的量子搜索算法研究

量子计算是基于量子力学的计算方法，绝热量子计算模型是解决NP完全问题的潜在计算模型，本项目基于绝热演化思想来研究具有广泛应用的计算机领域的基础问题- - 量子搜索算法。通过增加系统调整哈密顿量、修改插值方法及参数等来研究演化路径与绝热量子搜索算法性能之间的关系；通过分析现有的全局、局部和部分绝热量子搜索算法的特点来寻找施加绝热条件的规律。然后利用演化路径选取方法与绝热条件的施加机理来指导相关内容研究，通过在部分绝热区间上进行局部绝热演化来设计微局部绝热量子搜索算法，并寻找该问题的下界；同时通过研究绝热量子计算模型与量子线路模型的相互转换来深刻理解这两个模型之间的关系；项目还将通过研究绝热量子傅立叶变换来设计绝热量子计数算法。量子搜索算法具有广泛的应用，其可加速从P类到NP完全问题的大部分算法，项目的研究对理解绝热量子计算乃至量子计算的本质，促进量子计算和量子计算机的实用化具有重要意义。

绝热量子计算是基于连续时间变化的量子计算模型，该计算模型与基于量子线路的离散计算模型不同。对于一个量子系统可以用薛定谔方程来进行描述，在薛定谔方程中，系统的Hamilton量是关键，如果知道了系统的初态和系统Hamilton量，则系统任意时刻的状态都可以得到，如果系统的变化比较缓慢，则绝热定理可以保证，在以后任意时刻系统的状态将接近系统的临时基态，这样如果我们把一个问题按薛定谔方程进行编码，我们在系统演化完成后测量系统的状态即可得到问题的解。课题在此背景下特别对绝热量子搜索算法进行深入研究，主要研究了如下内容：.1）绝热演化方式对绝热量子算法性能的影响；.2）绝热量子搜索算法演化路径选取方法的研究；.3）基于微局部绝热演化的量子搜索算法研究；.4）绝热量子搜索算法与量子线路模型的关系研究；.5）量子计算的应用研究。.详细成果如下：.绝热量子算法可以分为全局绝热量子算法、局部绝热量子算法和部分绝热量子算法，如果系统的初态和终态正交，则三种算法都会引起计算失败，可以通过增加一个驱动Hamilton量来修正失败的演化算法。基于部分绝热的局部演化搜索算法具有相同的时间复杂度，进而证明局部绝热演化算法是最优的。微局部绝热搜索算法的性能要严格小于局部绝热量子搜索算法和部分绝热量子搜索算法，但是在算法复杂度上是它们具有相同的数量级。.课题分析了增加驱动哈密顿量、线形插值路径，一类特殊的非线性演化路径对绝热量子搜索算法性能的影响。.绝热量子算法具有与量子电路具有相同的性能，但在解决某些问题时更方便，特别是具有抗噪声能力。课题研究了在如何在绝热量子计算模型下模拟量子线路问题，同时可以构造多种最基本的量子线路门电路。.此外，还研究了量子计算来解决Deutsch–Jozsa问题，带辅助内存的无序数据库搜索问题，具有不同概率分布的绝热量子计算问题，采用绝热量子算法来进行布尔运算问题，量子机器学习问题等。.课题共在多种国际期刊和会议上发表论文22篇，其中SCI收录18篇。.课题的研究具有广泛的应用，其可加速从P 类到NP 完全问题的大部分算法，项目的研究对理解绝热量子计算乃至量子计算的本质，促进量子计算机的实用化具有重要意义。