基于量子游走的子图结构量子搜索算法研究

Quantum computers grant tremendous potential applications and designing appropriate quantum algorithms is the first step to explore the power of quantum computers. In the light of the features of quantum algorithms, it focuses on searching algorithms based on graph, transforms the problem into searching a sub-graph, and then constructs quantum searching algorithms adjusted according to the sub-graph structure. The contents consist mainly of: designing flexible and controllable quantum walk models, investigating quantum algorithms searching sub-graphs based on these quantum walk models. Especially designing quantum searching algorithms for NP problems, such as Hamilton circuit problem, SAT problems and travelling salesman problem, and analyzing the complexity, finding the boundaries of quantum algorithms in solving NP problems, promoting the theory of quantum algorithms and quantum complexity.

量子计算机蕴藏着巨大的潜在应用价值，设计合适的量子算法是发掘量子计算机成功应用的前提条件。根据量子算法设计的特点，本研究拟从基于图论的搜索算法出发，将求解问题的过程转化为图上的子图搜索过程，从子图的结构特性和约束中设计相应的量子搜索算法。主要研究内容包括：研究灵活可控的量子游走模型，以此为基础研究在图中搜索指定子图结构的量子搜索算法，特别针对NP类问题，如哈密尔顿回路问题、SAT问题和旅行商问题设计量子算法，并分析复杂性，探索量子算法在解决NP类问题时的复杂性上下界，以推动量子算法与量子计算复杂性理论的发展。

量子计算是应用量子力学效应来进行有效计算的新的计算方式，在过去的十几年里这种新的计算方式吸引了大批的物理学家、数学家和计算机科学家。在数学上，人们则努力于研究量子编码、设计新的量子算法。在计算机科学领域，人们致力于设计量子程序语言、量子算法，研究量子计算复杂性以及量子计算模型。搜索算法是经典算法中非常重要的一类算法，同样的，量子搜索算法也是一类重要的量子算法。.本项目主要研究了图上的一般性量子搜索算法，也即在图上搜索一般子图的算法。我们嵌套使用Johnson图上的多重散射量子游走，每一层量子游走的目标是寻找给定子图中的一个点，以深度优先或者广优先的方式从子图中选取下一个搜索的点。在搜索最后一个点的同时，利用graph collision的量子判断算法来检测算法是否搜索到了正确的子图结构。我们以搜索简单的星型图为例，构造了具体算法，并在这种简单情况来得到了算法的查询复杂度。虽然这种算法的复杂度随子图结构的复杂度递增，但其是可行的设计一般搜索算法的途径。