Abstract: As a universal computational model in quantum computing, the quantum walk is employed in secure communication, quick query, similar calculation, graph mining, etc. At present, researchers have paid limited attention to the design, development, and relationship between models and algorithms of the quantum walk. Further, the theoreticals advantages of the quantum walk on graphs in graph computing are neglected. Aiming at the quantum walk model and algorithms for graph data, firstly, the core design strategy and theoretical advantages of quantum walks are analyzed, the construction form of significant operators and spatial dimension characteristics of relevant algorithms are summarized, and the logical relationship between model and algorithm is clarified. Secondly, according to the classification of discrete-time and continuous-time, the research advances and design difficulties of the quantum walk model are summarized, and the evolutionary trend of quantum walk extending from regular graphs to irregular graphs is concluded. Furthermore, around the similarity calculation of graphs, spatial search, and graph mining, the research progress of quantum walk algorithms is reviewed, and the technical characteristics, advantages and shortcomings of relevant algorithms are analyzed. Finally, from the perspectives of efficiency optimization, accuracy improvement, unitary constraints, and graph reconstruction, the future research directions of the quantum walk models and algorithms are prospected.

Key words: quantum computing, quantum walk, graph-structural data, discrete-time, continuous-time, graph mining

摘要： 作为量子计算的通用计算模型，量子行走广泛应用于安全通信、快速搜索、相似性计算以及图挖掘等领域。现阶段研究者对量子行走的设计思路、未来发展以及模型与算法间的相互关系关注甚少，忽略了量子行走的量子特性在图计算等应用中的理论优势。聚焦面向图数据的量子行走模型及算法，首先，分析量子行走的核心设计策略及其理论优势，归纳相关算法核心算符的构造形式与空间维度特征，厘清模型与算法间的逻辑联系；其次，依据离散时间和连续时间的分类，梳理不同图数据上量子行走模型的研究进展及设计难点，总结量子行走从规则图向不规则图上扩展的演化趋势；进一步，围绕图相似性计算、空间搜索以及图挖掘三项应用系统地介绍量子行走算法的研究进展，分析相关算法的技术特征、优势及不足；最后，从效率优化、精度提升、幺正约束以及图重构等角度，对面向图数据的量子行走模型与算法未来发展方向进行了展望。

关键词: 量子计算, 量子行走, 图结构数据, 离散时间, 连续时间, 图挖掘