This thesis studies 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 a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. \n \nWe begin by finding the eigenvalues of matrices describing the quantum walk for regular graphs. We also show that if two graphs are isomorphic, then the corresponding matrices produced by the procedure of Emms et al. are cospectral. We then look at the entries of the cube of the transition matrix and find an expression for the matrices produced by the procedure of Emms et al. in terms of the adjacency matrix and incidence matrices of the graph.
This thesis studies 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 a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. \n \nWe begin by finding the eigenvalues of matrices describing the quantum walk for regular graphs. We also show that if two graphs are isomorphic, then the corresponding matrices produced by the procedure of Emms et al. are cospectral. We then look at the entries of the cube of the transition matrix and find an expression for the matrices produced by the procedure of Emms et al. in terms of the adjacency matrix and incidence matrices of the graph.
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.
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.
Let G be a strongly regular graph of prime order p with connection degree k≥6. We prove that the \emph{quantum walk characteristic polynomial} χq(G,λ):=det(λI−UG), where UG is the coined quantum walk operator on G, completely determines G up to isomorphism within the class of strongly regular graphs of the same order.
The proof proceeds in three steps. First, we show that UG block-diagonalizes under the discrete Fourier transform over Zp, yielding p blocks UG(j) of size k×k. Second, we prove an explicit formula χq(UG(j),λ)=(λ−1)(k−2)/2(λ+1)(k−2)/2(λ2−k2AG(j)λ+1), from which the Fourier coefficient AG(j) is recovered as the unique real part of an eigenvalue of UG(j) distinct from ±1. Third, the inverse discrete Fourier transform recovers the connection set S of G, and Turner's theorem (1967) identifies G up to isomorphism. As a consequence, graph isomorphism is decidable in polynomial time within this class using the quantum walk spectrum, without resorting to the general quasi-polynomial algorithm of Babai (2016).
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 probabilistically compute the spectrum of the line intersection graphs of two non-isomorphic generalized quadrangles of order (52,5) under this matrix and thus provide strongly regular counter-examples to the conjecture.
We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs. The latter class is a generalization of the former. We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph K2,2 and the complete tripartite graph K2,2,2. We then show that, if a connected strongly walk-regular graph that is not a strongly regular graph admits perfect state transfer, then its spectrum must be of the form {[k]1,[2k]α,[0]β,[−2k]γ}, and we enumerate all feasible spectra of this form up to k=20 with the help of a computer. These results are obtained using techniques from algebraic number theory and spectral graph theory, particularly through the analysis of eigenvalues and eigenprojections of a normalized adjacency matrix. While the setting is in quantum walks, the core discussion is developed entirely within the framework of spectral graph theory.
The join X ∨ Y of two graphs X and Y is the graph obtained by joining each vertex of X to each vertex of Y . We explore the behaviour of a continuous quantum walk on a join graph with positive edge weights having the adjacency matrix or Laplacian matrix as its associated Hamiltonian, where the underlying graphs are assumed to be regular when dealing with the adjacency matrix. We characterize strong cospectrality, periodicity and perfect state transfer (PST) in a join graph. We also determine conditions in which strong cospectrality, periodicity and PST are preserved in the join. Under certain conditions, we show that there are graphs with no PST that exhibit PST when joined with another graph. We also show that | | U M ( X ∨ Y , t ) u , v | − | U M ( X , t ) u , v | | ≤ 2 | V ( X ) | for all vertices u and v of X , where U M ( X ∨ Y , t ) and U M ( X , t ) denote the transition matrices of X ∨ Y and X respectively relative to the adjacency or Laplacian matrix. We demonstrate that the bound 2 | V ( X ) | is tight for infinite families of graphs.