Please wait a minute...
Chin. Phys. B, 2013, Vol. 22(5): 050304    DOI: 10.1088/1674-1056/22/5/050304
GENERAL Prev   Next  

Finding symmetries of trees using continuous-time quantum walk

Wu Jun-Jie (吴俊杰)a b, Zhang Bai-Da (张百达)a b, Tang Yu-Hua (唐玉华)a b, Qiang Xiao-Gang (强晓刚)c, Wang Hui-Quan (王会权)a b
a State Key Laboratory of High Performance Computing, National University of Defense Technology, Changsha 410073, China;
b School of Computer, National University of Defense Technology, Changsha 410073, China;
c Center for Quantum Photonics, H. H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol,Merchant Venturers Building, Woodland Road, Bristol BS8 1UB, UK
Abstract  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.
Keywords:  quantum walk      tree      symmetry      automorphism  
Received:  08 September 2012      Revised:  23 November 2012      Accepted manuscript online: 
PACS:  03.67.-a (Quantum information)  
  02.10.Ox (Combinatorics; graph theory)  
  89.20.Ff (Computer science and technology)  
  07.05.Tp (Computer modeling and simulation)  
Fund: Project supported by the National Natural Science Foundation of China (Grant No. 61003082).
Corresponding Authors:  Wu Jun-Jie     E-mail:

Cite this article: 

Wu Jun-Jie (吴俊杰), Zhang Bai-Da (张百达), Tang Yu-Hua (唐玉华), Qiang Xiao-Gang (强晓刚), Wang Hui-Quan (王会权) Finding symmetries of trees using continuous-time quantum walk 2013 Chin. Phys. B 22 050304

[1] Kempe J 2003 Contemporary Physics 44 307
[2] Shenvi N, Kempe J and Whaley K B 2003 Phys. Rev. A 67 052307
[3] Childs A M and Goldstone J 2004 Phys. Rev. A 70 022314
[4] Tulsi A 2008 Phys. Rev. A 78 012310
[5] Somma R D, Boixo S, Barnum H and Knill E 2008 Phys. Rev. Lett. 101 130504
[6] Childs A M 2009 Phys. Rev. Lett. 102 180501
[7] Lovett N B, Cooper S, Everitt M, Trevers M and Kendon V 2010 Phys. Rev. A 81 042330
[8] Berry S D and Wang J B 2011 Phys. Rev. A 83 042317
[9] Gamble J K, Friesen M, Zhou D, Joynt R and Coppersmith S N 2010 Phys. Rev. A 81 052313
[10] Qiang X, Yang X, Wu J and Zhu X 2012 J. Phys. A: Math. Theor. 45 045305
[11] Forsyth D A and Ponce J 2002 Computer Vision: A Modern Approach (Upper Saddle River: Prentice Hall Professional Technical Reference)
[12] Kandel A, Bunke H and Last M 2010 Applied Graph Theory in Computer Vision and Pattern Recognition (1st edn.) (Berlin: Springer)
[13] Brügger A, Bunke H, Dickinson P and Riesen K 2008 (Perner P, ed.) Lecture Notes in Computer Science Vol. 5077 (Heidelberg: Springer) pp. 298-312
[14] Artymiuk P J, Spriggs R V and Willett P 2005 Journal of the American Society for Information Science and Technology 56 518
[15] Fortin S 1996 Technical Report 96-20, Department of Computing Science, University of Alberta
[16] Zhang B D, Wu J J, Tang Y H and Zhou J 2012 Physica Scripta 86 025006
[17] Zhang J Y, Sun W G and Chen G R 2012 Chin. Phys. B 21 38901
[18] Lin F and Bao J D 2011 Chin. Phys. B 20 40502
[19] Li K P 2010 Chin. Phys. B 19 30519
[20] Hu K and Tang Y 2006 Chin. Phys. 15 2782
[21] Yang X, Liao X, Xu W, Song J, Hu Q, Su J, Xiao L, Lu K, Dou Q, Jiang J and Yang C 2010 Frontiers of Computer Science in China 4 445
[22] Yang X, Liao X, Lu K, Hu Q, Song J and Su J 2011 Journal of Computer Science and Technology 26 344
[23] Broome M A, Fedrizzi A, Lanyon B P, Kassal I, Aspuru-Guzik A and White A G 2010 Phys. Rev. Lett. 104 153602
[24] Zähringer F, Kirchmair G, Gerritsma R, Solano E, Blatt R and Roos C F 2010 Phys. Rev. Lett. 104 100503
[25] Schreiber A, Cassemiro K N, Potoček V, Gábris A, Mosley P J, Andersson E, Jex I and Silberhorn C 2010 Phys. Rev. Lett. 104 050502
[26] Douglas B L and Wang J B 2009 Phys. Rev. A 79 052335
[27] Xu Y Y, Zhou F, Chen L, Xie Y, Xue P and Feng M 2012 Chin. Phys. B 21 40304
[28] Peruzzo A, Lobino M, Matthews J C F, Matsuda N, Politi A, Poulios K, Zhou X, Lahini Y, Ismail N, Wörhoff K, Bromberg Y, Silberberg Y, Thompson M G and OBrien J L 2010 Science 329 1500
[29] Karski M, Förster L, Choi J M, Steffen A, Alt W, Meschede D and Widera A 2009 Science 325 174
[30] Tsomokos D I 2011 Phys. Rev. A 83 052315
[31] Mülken O and Blumen A 2011 Physics Reports 502 37
[32] Cameron P J 2004 Automorphisms of Graphs, Topics in Algebraic Graph Theory (Cambridge: Cambridge University Press)
[33] De Fraysseix H 1999 (J Kratochvíyl, ed.) Lecture Notes in Computer Science Vol. 1731 (Berlin: Springer) pp. 276-285
[34] Douglas B L and Wang J B 2008 J. Phys. A: Math. Theor. 41 075303
[1] Chiral symmetry protected topological nodal superconductingphase and Majorana Fermi arc
Mei-Ling Lu(卢美玲), Yao Wang(王瑶), He-Zhi Zhang(张鹤之), Hao-Lin Chen(陈昊林), Tian-Yuan Cui(崔天元), and Xi Luo(罗熙). Chin. Phys. B, 2023, 32(2): 027301.
[2] Site selective 5f electronic correlations in β-uranium
Ruizhi Qiu(邱睿智), Liuhua Xie(谢刘桦), and Li Huang(黄理). Chin. Phys. B, 2023, 32(1): 017101.
[3] Influence of coupling asymmetry on signal amplification in a three-node motif
Xiaoming Liang(梁晓明), Chao Fang(方超), Xiyun Zhang(张希昀), and Huaping Lü(吕华平). Chin. Phys. B, 2023, 32(1): 010504.
[4] Evolution of polarization singularities accompanied by avoided crossing in plasmonic system
Yi-Xiao Peng(彭一啸), Qian-Ju Song(宋前举), Peng Hu(胡鹏), Da-Jian Cui(崔大健), Hong Xiang(向红), and De-Zhuan Han(韩德专). Chin. Phys. B, 2023, 32(1): 014201.
[5] Recent advances of defect-induced spin and valley polarized states in graphene
Yu Zhang(张钰), Liangguang Jia(贾亮广), Yaoyao Chen(陈瑶瑶), Lin He(何林), and Yeliang Wang(王业亮). Chin. Phys. B, 2022, 31(8): 087301.
[6] Conservation of the particle-hole symmetry in the pseudogap state in optimally-doped Bi2Sr2CuO6+δ superconductor
Hongtao Yan(闫宏涛), Qiang Gao(高强), Chunyao Song(宋春尧), Chaohui Yin(殷超辉), Yiwen Chen(陈逸雯), Fengfeng Zhang(张丰丰), Feng Yang(杨峰), Shenjin Zhang(张申金), Qinjun Peng(彭钦军), Guodong Liu(刘国东), Lin Zhao(赵林), Zuyan Xu(许祖彦), and X. J. Zhou(周兴江). Chin. Phys. B, 2022, 31(8): 087401.
[7] Quantum search of many vertices on the joined complete graph
Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Chin. Phys. B, 2022, 31(7): 070504.
[8] Local sum uncertainty relations for angular momentum operators of bipartite permutation symmetric systems
I Reena, H S Karthik, J Prabhu Tej, Sudha, A R Usha Devi, and A K Rajagopal. Chin. Phys. B, 2022, 31(6): 060301.
[9] Dynamical quantum phase transition in XY chains with the Dzyaloshinskii-Moriya and XZY-YZX three-site interactions
Kaiyuan Cao(曹凯源), Ming Zhong(钟鸣), and Peiqing Tong(童培庆). Chin. Phys. B, 2022, 31(6): 060505.
[10] Parity-time symmetric acoustic system constructed by piezoelectric composite plates with active external circuits
Yang Zhou(周扬), Zhang-Zhao Yang(杨彰昭), Yao-Yin Peng(彭尧吟), and Xin-Ye Zou(邹欣晔). Chin. Phys. B, 2022, 31(6): 064304.
[11] A nonlocal Boussinesq equation: Multiple-soliton solutions and symmetry analysis
Xi-zhong Liu(刘希忠) and Jun Yu(俞军). Chin. Phys. B, 2022, 31(5): 050201.
[12] Efficient quantum private comparison protocol based on one direction discrete quantum walks on the circle
Jv-Jie Wang(王莒杰), Zhao Dou(窦钊), Xiu-Bo Chen(陈秀波), Yu-Ping Lai(赖裕平), and Jian Li(李剑). Chin. Phys. B, 2022, 31(5): 050308.
[13] Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube
Yao-Yao Jiang(姜瑶瑶), Peng-Cheng Chu(初鹏程), Wen-Bin Zhang(张文彬), and Hong-Yang Ma(马鸿洋). Chin. Phys. B, 2022, 31(4): 040307.
[14] Residual symmetries, consistent-Riccati-expansion integrability, and interaction solutions of a new (3+1)-dimensional generalized Kadomtsev—Petviashvili equation
Jian-Wen Wu(吴剑文), Yue-Jin Cai(蔡跃进), and Ji Lin(林机). Chin. Phys. B, 2022, 31(3): 030201.
[15] High-energy x-ray diffraction study on phase transition asymmetry of plastic crystal neopentylglycol
Zhe Zhang(张哲), Yan-Na Chen(陈艳娜), Ji Qi(齐迹), Zhao Zhang(张召), Koji Ohara, Osami Sakata, Zhi-Dong Zhang(张志东), and Bing Li(李昺). Chin. Phys. B, 2022, 31(3): 036802.
No Suggested Reading articles found!