TAILIEUCHUNG - Báo cáo toán học: "uantum Walks on Regular Graphs and Eigenvalues"

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 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học