Finding symmetries of trees using continuous-time quantum walk

doi:10.1088/1674-1056/22/5/050304

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(N³) 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: junjiewu@nudt.edu.cn

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]	Demonstrate chiral spin currents with nontrivial interactions in superconducting quantum circuit Xiang-Min Yu(喻祥敏), Xiang Deng(邓翔), Jian-Wen Xu(徐建文), Wen Zheng(郑文), Dong Lan(兰栋), Jie Zhao(赵杰), Xinsheng Tan(谭新生), Shao-Xiong Li(李邵雄), and Yang Yu(于扬). Chin. Phys. B, 2023, 32(4): 047104.
[2]	Conformable fractional heat equation with fractional translation symmetry in both time and space W S Chung, A Gungor, J Kříž, B C Lütfüoǧlu, and H Hassanabadi. Chin. Phys. B, 2023, 32(4): 040202.
[3]	An optimized infinite time-evolving block decimation algorithm for lattice systems Junjun Xu(许军军)^†. Chin. Phys. B, 2023, 32(4): 040303.
[4]	Lie symmetry analysis and invariant solutions for the (3+1)-dimensional Virasoro integrable model Hengchun Hu(胡恒春) and Yaqi Li(李雅琦). Chin. Phys. B, 2023, 32(4): 040503.
[5]	Chiral symmetry protected topological nodal superconducting phase 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.
[6]	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.
[7]	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.
[8]	Site selective 5f electronic correlations in β-uranium Ruizhi Qiu(邱睿智), Liuhua Xie(谢刘桦), and Li Huang(黄理). Chin. Phys. B, 2023, 32(1): 017101.
[9]	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.
[10]	Conservation of the particle-hole symmetry in the pseudogap state in optimally-doped Bi₂Sr₂CuO_6+δ 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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	A nonlocal Boussinesq equation: Multiple-soliton solutions and symmetry analysis Xi-zhong Liu(刘希忠) and Jun Yu(俞军). Chin. Phys. B, 2022, 31(5): 050201.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Finding symmetries of trees using continuous-time quantum walk

Cite this article:

Online attention