论文部分内容阅读
在20世纪90年代中期，Shor量子因子分解算法和Grover量子搜索算法的相继提出，引起了人们对量子计算与量子信息的极大兴趣，这是因为这两个算法充分展示了量子计算机在某些方面能够从根本上超越经典计算机的计算能力。近年来，量子行走引起了理论研究者的关注，主要是因为经典随机行走在计算机科学、生物学、物理学等多个学科有着广泛的应用，而量子行走可看成经典随机行走在量子系统中的自然推广，因此人们希望能够借助于量子行走发现更多高效的量子算法。 本文在介绍量子算法基础知识和Grover算法的基础上，分别描述了两种离散量子行走模型:硬币量子行走和散射量子行走，并将硬币量子行走与经典随机行走进行了分析对比;然后讨论了第一个基于量子行走的搜索算法—SKW算法，该算法与Grover算法搜索速度一样，但其Oracle算子作用的空间维数小于Grover搜索算法，这表明SKW算法相对于Grover算法来说在物理上更易于实现。 本文最后集中讨论了在星图上的散射量子行走。首先证明了在星图上两种离散量子行走的酉等价关系;接着提出了一种在星图上的散射量子行走搜索算法。通过对本文所提出的算法进行分析，表明该算法与Grover算法的搜索速度一样，但是当要搜索的目标数目多于总数的1/3时成功概率大于Grover算法。