Research Advances of Quantum Walk Models and Algorithms for Graph Data

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.

Keywords

• quantum computing; quantum walk; graph-structural data; discrete-time; continuous-time; graph mining