Research And Analysis On Discrete-time Quantum Walks On The Cayley Graph Of The Dihedral Group

In this thesis,discrete-time quantum walks on the dihedral group attach much attention.Group is an abstract concept.Cayley graphs,as diagrammatic counterparts of groups,are convenient means to study quantum walks exploiting the group-theoretical machinery.Thus we study and analyze discrete-time quantum walks on the Cayley graph of the dihedral group,including quantum walk without memory on the Cayley graph of the dihedral group,quantum walk with memory on the Cayley graph of the dihedral group,and three-state quantum walk on the Cayley graph of the dihedral group.The details are as follows:Firstly,in view of the characteristics of the finite dihedral group generated by a rotation and a reflection,the model of quantum walk without memory on the Cayley graph of the dihedral group is proposed using special encoding mode.Spectrum analysis is conducted by using Fourier Transform.The one-to-one correspondence between quantum walk without memory on the Cayley graph of the dihedral group and quantum walk with one-step memory on the cycle is proposed.Moreover,basic probabilistic properties of the walk are further studied using numerical simulation method.Secondly,by adding one-step memory to enrich the model of quantum walk without memory on the Caylay graph of the dihedral group,the model of quantum walk with memory on the Caylay graph of the dihedral group is constructed.Fourier Transform is used to analyze the walk.The concrete forms of probability distribution and time-average probability distribution are given.According to the one-to-one correspondence between quantum walks with memory on regular graphs and quantum walks without memory on the corresponding line digraphs,the diagrammatic counterpart of quantum walk with one-step memory on the Cayley graph of the dihedral group is presented.Moreover,basic probabilistic properties of the walk are further studied using numerical simulation method.Furthermore,the similarities and differences between quantum walks without memory and quantum walks with memory are discussed in terms of line,cycle and the Cayley graph of the dihedral group.Thirdly,by extending coin operator from two-dimensional unitary matrix to three-dimensional unitary matrix,three-state quantum walk on the Caylay graph of the dihedral group is constructed.Fourier transform is used to analyze the walk.Moreover,basic probabilistic properties of the walk are further studied using numerical simulation method.Furthermore,the similarities and differences between coined quantum walks using a two-dimensional coin(i.e.two-state quantum walk)and coined quantum walks using a three-dimensional coin(i.e.three-state quantum walk)are discussed in terms of line,cycle and the Cayley graph of the dihedral group.In conclusion,this thesis has carried out a series of research work around the discrete quantum walk on the Cayley graph of the dihedral group,and further expanded the theoretical study of quantum walks on the Cayley graph of the non-Abelian group.