Finding symmetries of trees using continuous-time quantum walk

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

中国物理B ›› 2013, Vol. 22 ›› Issue (5): 50304-050304.doi: 10.1088/1674-1056/22/5/050304

Finding symmetries of trees using continuous-time quantum walk

吴俊杰^{a b}, 张百达^{a b}, 唐玉华^{a b}, 强晓刚^c, 王会权^{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

收稿日期:2012-09-08 修回日期:2012-11-23 出版日期:2013-04-01 发布日期:2013-04-01
基金资助:
Project supported by the National Natural Science Foundation of China (Grant No. 61003082).

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

Received:2012-09-08 Revised:2012-11-23 Online:2013-04-01 Published:2013-04-01
Contact: Wu Jun-Jie E-mail:junjiewu@nudt.edu.cn
Supported by:
Project supported by the National Natural Science Foundation of China (Grant No. 61003082).

摘要/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.

关键词: quantum walk, tree, symmetry, automorphism

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.

Key words: quantum walk, tree, symmetry, automorphism

中图分类号: (Quantum information)

03.67.-a

02.10.Ox (Combinatorics; graph theory) 89.20.Ff (Computer science and technology) 07.05.Tp (Computer modeling and simulation)

吴俊杰, 张百达, 唐玉华, 强晓刚, 王会权. Finding symmetries of trees using continuous-time quantum walk[J]. 中国物理B, 2013, 22(5): 50304-050304.

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

参考文献 34

[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

Finding symmetries of trees using continuous-time quantum walk

Finding symmetries of trees using continuous-time quantum walk

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 34

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Xiang-Min Yu(喻祥敏), Xiang Deng(邓翔), Jian-Wen Xu(徐建文), Wen Zheng(郑文), Dong Lan(兰栋), Jie Zhao(赵杰), Xinsheng Tan(谭新生), Shao-Xiong Li(李邵雄), and Yang Yu(于扬). Demonstrate chiral spin currents with nontrivial interactions in superconducting quantum circuit[J]. 中国物理B, 2023, 32(4): 47104-047104.
[2]	W S Chung, A Gungor, J Kříž, B C Lütfüoǧlu, and H Hassanabadi. Conformable fractional heat equation with fractional translation symmetry in both time and space[J]. 中国物理B, 2023, 32(4): 40202-040202.
[3]	Junjun Xu(许军军)^†. An optimized infinite time-evolving block decimation algorithm for lattice systems[J]. 中国物理B, 2023, 32(4): 40303-040303.
[4]	Hengchun Hu(胡恒春) and Yaqi Li(李雅琦). Lie symmetry analysis and invariant solutions for the (3+1)-dimensional Virasoro integrable model[J]. 中国物理B, 2023, 32(4): 40503-040503.
[5]	Mei-Ling Lu(卢美玲), Yao Wang(王瑶), He-Zhi Zhang(张鹤之), Hao-Lin Chen(陈昊林), Tian-Yuan Cui(崔天元), and Xi Luo(罗熙). Chiral symmetry protected topological nodal superconducting phase and Majorana Fermi arc[J]. 中国物理B, 2023, 32(2): 27301-027301.
[6]	Ruizhi Qiu(邱睿智), Liuhua Xie(谢刘桦), and Li Huang(黄理). Site selective 5f electronic correlations in β-uranium[J]. 中国物理B, 2023, 32(1): 17101-017101.
[7]	Xiaoming Liang(梁晓明), Chao Fang(方超), Xiyun Zhang(张希昀), and Huaping Lü(吕华平). Influence of coupling asymmetry on signal amplification in a three-node motif[J]. 中国物理B, 2023, 32(1): 10504-010504.
[8]	Yi-Xiao Peng(彭一啸), Qian-Ju Song(宋前举), Peng Hu(胡鹏), Da-Jian Cui(崔大健), Hong Xiang(向红), and De-Zhuan Han(韩德专). Evolution of polarization singularities accompanied by avoided crossing in plasmonic system[J]. 中国物理B, 2023, 32(1): 14201-014201.
[9]	Yu Zhang(张钰), Liangguang Jia(贾亮广), Yaoyao Chen(陈瑶瑶), Lin He(何林), and Yeliang Wang(王业亮). Recent advances of defect-induced spin and valley polarized states in graphene[J]. 中国物理B, 2022, 31(8): 87301-087301.
[10]	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(周兴江). Conservation of the particle-hole symmetry in the pseudogap state in optimally-doped Bi₂Sr₂CuO_6+δ superconductor[J]. 中国物理B, 2022, 31(8): 87401-087401.
[11]	Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Quantum search of many vertices on the joined complete graph[J]. 中国物理B, 2022, 31(7): 70504-070504.
[12]	Yang Zhou(周扬), Zhang-Zhao Yang(杨彰昭), Yao-Yin Peng(彭尧吟), and Xin-Ye Zou(邹欣晔). Parity-time symmetric acoustic system constructed by piezoelectric composite plates with active external circuits[J]. 中国物理B, 2022, 31(6): 64304-064304.
[13]	I Reena, H S Karthik, J Prabhu Tej, Sudha, A R Usha Devi, and A K Rajagopal. Local sum uncertainty relations for angular momentum operators of bipartite permutation symmetric systems[J]. 中国物理B, 2022, 31(6): 60301-060301.
[14]	Kaiyuan Cao(曹凯源), Ming Zhong(钟鸣), and Peiqing Tong(童培庆). Dynamical quantum phase transition in XY chains with the Dzyaloshinskii-Moriya and XZY-YZX three-site interactions[J]. 中国物理B, 2022, 31(6): 60505-060505.
[15]	Xi-zhong Liu(刘希忠) and Jun Yu(俞军). A nonlocal Boussinesq equation: Multiple-soliton solutions and symmetry analysis[J]. 中国物理B, 2022, 31(5): 50201-050201.