Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Quantum Walks on Regular Graphs and Eigenvalues. | Quantum Walks on Regular Graphs and Eigenvalues Chris Godsil Department of Combinatorics Optimization University of Waterloo Waterloo Ontario Canada cdgodsil@ Krystal Guo Department of Combinatorics Optimization University of Waterloo Waterloo Ontario Canada kguo@ Submitted Dec 16 2010 Accepted Jul 4 2011 Published Aug 12 2011 Mathematics Subject Classification 05C50 81P68 Abstract We study the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms Hancock Severini and Wilson in 2006 that the spectrum of S U3 a matrix based on the amplitudes of walks in the quantum walk distinguishes strongly regular graphs. We find the eigenvalues of S U and S U2 for regular graphs and show that S U2 S U 2 I. 1 Introduction A discrete-time quantum walk is a quantum process on a graph whose state vector is governed by a matrix called the transition matrix. In 3 2 Emms Severini Wilson and Hancock propose that the quantum walk transition matrix can be used to distinguish between non-isomorphic graphs. Let U G and U H be the transition matrices of quantum walks on G and H respectively. Given a matrix M the positive support of M denoted S M is the matrix obtained from M as follows S M k I1 if Mij 0 S M i j s 0 otherwise. Theorem. If G and H are isomorphic regular graphs then S U G 3 and S U H 3 are cospectral. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P165 1 The authors of 2 3 propose that the converse of Theorem is also true they conjecture that the spectrum of the matrix S U3 distinguishes strongly regular graphs. After experiments on a large set of graphs no strongly regular graph is known to have a cospectral mate with respect to this invariant. If the conjecture is true it would yield a classical polynomial-time algorithm for the Graph Isomorphism Problem for strongly regular graphs but there do not seem to be strong grounds for believing the conjecture . In this paper we will find the spectra of two matrices .
