论文部分内容阅读
由于量子计算具有与经典计算不同的特性,因此量子算法在某些问题上具有量子加速。本文主要着眼于量子算法中的两个部分,量子搜索算法以及量子优化算法。为了验证量子计算的优越性,本文提出了三种算法,分别为基于连续变量的不动点量子搜索算法、基于离散变量的多层量子搜索算法以及基于连续变量的量子梯度算法,并对以上算法进行了详细介绍和分析。具体内容如下:1、现有的量子搜索算法主要研究离散搜索问题,于是我们提出了基于连续变量计算模型的不动点量子搜索算法来解决连续搜索问题。对于连续搜索问题,我们通过构造相应的量子态和酉变换,从而设计出了不动点量子搜索算法,并计算了对于连续搜索问题的量子算法复杂度的下界。另外,基于前人的工作,本文提出了最优的不动点量子搜索算法,并且给出了算法中利用oracle构造的具体电路。为了验证该算法的有效性,我们将其运用在了一个具体优化问题上进行仿真,并且给出了一个可以物理实现的oracle电路。2、对于搜索算法,我们目前已知最优的量子搜索算法具有平方加速。为了实现更优的量子搜索算法,我们探讨了量子多层搜索算法。假定存在相应的量子oracle,其能够使目标态整体翻转,而非作用在目标态的基底上进行翻转。搜索问题大致可以分为多条件搜索问题和单条件搜索问题,本文论述了这两种问题都可以用多层量子搜索算法实现。另外,我们借助不动点量子搜索算法,提出了可行的替代方案来实现多层量子搜索,并对该算法进行了误差和复杂度的分析,证明了该算法在处理已知统计规律的大数据搜索问题时具有指数加速,这体现了量子计算的优越性。3、除了量子搜索算法,本文还讨论了量子优化算法,提出并分析了基于连续变量的梯度下降算法,还给出了具体的量子电路。在连续变量计算框架下,其存在天然的微分器,于是本文通过特殊构造,将这一性质运用在了算法设计中,从而实现了量子梯度下降算法。另外,本文采用的是全酉变换电路结构,中间过程没有用到量子测量,因此不需要有足够多的复制态来确保算法的成功。本文提出的三个量子算法,相较于经典算法具有量子加速,体现了量子计算的优势。本文的相关工作,丰富了量子搜索以及量子优化算法的模型,为后续更深入的研究提供了新的方法和思路。