An enhanced classical approach to graph isomorphism using continuous-time quantum walk

作者：Qiang, Xiaogang^*; Yang, Xuejun; Wu, Junjie; Zhu, Xuan

来源：Journal of Physics A-Mathematical and Theoretical, 2012, 45(4): 045305.

DOI：10.1088/1751-8113/45/4/045305

Studies on graph isomorphism play an important role in graph research, and graph isomorphism algorithms have a wide range of applications in image matching, pattern recognition, computer vision, biochemistry and other fields. Previous research demonstrated that involving discrete-time quantum walk in the graph isomorphism algorithm could achieve complexity O(N(7)) for general graphs, since quantum walk could be utilized as a new toolbox for solving graph problems. We develop an enhanced classical approach to graph isomorphism using continuous-time quantum walk, which has lower complexity O(N(5)) and can effectively distinguish the graphs that are generally considered difficult. In addition, we define a graph similarity measure based on the proposed algorithm, which can be used for graph isomorphism and graph clustering. In the experiment, we test a wide variety of classes of graphs; the results show that the algorithm has a wide range of applications rather than being limited to a specific type of graph.

• 出版日期2012-2-3
• 单位中国人民解放军国防科学技术大学