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 sy...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（N3） 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.展开更多
基金Project supported by the National Natural Science Foundation of China (Grant No. 61003082)
文摘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（N3） 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.
