Finding tree symmetries using continuous-time quantum walk
Junjie Wu, Bai-Da Zhang, Yuhua Tang, Xiaogang Qiang, Huiquan Wang · Chinese Physics B · 2013
Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the symmetry of a graph, especially that of a tree. Firstly, we prove in mathematics that the symmetry of a graph is highly related to quantum walk. Secondly, we propose an algorithm based on the continuous-time quantum walk to compute the symmetry of a tree. Our algorithm has better time complexity O( N 3 ) than the current best algorithm. Finally, through testing three types of 10024 trees, we find that the symmetry of a tree can be found with an extremely high efficiency with the help of the continuous-time quantum walk.