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^+(U^3)

, 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^+(U^2)

for regular graphs.

DOI: 10.48550/arxiv.1011.5460

Related papers

Quantum Walks on Regular Graphs and Eigenvalues

Chris D. Godsil, Krystal Guo

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^+(U^3)$ , 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^+(U^2)$ for regular graphs and show that $S^+(U^2) = S^+(U)^2 + I$ .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^+(U^3)$, 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^+(U^2)$ for regular graphs and show that $S^+(U^2) = S^+(U)^2 + I$.

The Electronic Journal of CombinatoricsAug 12, 201131 citations

Quantum Walks on Strongly Regular Graphs

Krystal Guo

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.

Aug 30, 20104 citations

Quantum Walks on Generalized Quadrangles

Chris D. Godsil, Krystal Guo, Tor G. J. Myklebust

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^+(U^3)$ , 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 $(5^2,5)$ under this matrix and thus provide strongly regular counter-examples to the conjecture.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^+(U^3)$, 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 $(5^2,5)$ under this matrix and thus provide strongly regular counter-examples to the conjecture.

arXiv:1511.01962The Electronic Journal of CombinatoricsOct 20, 20175 citations

The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde

Diego Roldan

Let $G$ be a strongly regular graph of prime order $p$ with connection degree $k \geq 6$ . We prove that the \emph{quantum walk characteristic polynomial} $χ_q(G,λ) \coloneqq \det(λI - U_G)$ , where $U_G$ 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 $U_G$ block-diagonalizes under the discrete Fourier transform over $\Z_p$ , yielding $p$ blocks $U_G^{(j)}$ of size $k \times k$ . Second, we prove an explicit formula $χ_q\!\bigl(U_G^{(j)}, λ\bigr) = (λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2} \!\left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k}\,λ+ 1\right),$ from which the Fourier coefficient $\widehat{A}_G(j)$ is recovered as the unique real part of an eigenvalue of $U_G^{(j)}$ distinct from $\pm 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).Let $G$ be a strongly regular graph of prime order $p$ with connection degree $k \geq 6$. We prove that the \emph{quantum walk characteristic polynomial} $χ_q(G,λ) \coloneqq \det(λI - U_G)$, where $U_G$ 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 $U_G$ block-diagonalizes under the discrete Fourier transform over $\Z_p$, yielding $p$ blocks $U_G^{(j)}$ of size $k \times k$. Second, we prove an explicit formula \[ χ_q\!\bigl(U_G^{(j)}, λ\bigr) = (λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2} \!\left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k}\,λ+ 1\right), \] from which the Fourier coefficient $\widehat{A}_G(j)$ is recovered as the unique real part of an eigenvalue of $U_G^{(j)}$ distinct from $\pm 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).

quant-pharXiv:2604.01507Apr 3, 20260 citations

Strongly regular and strongly walk-regular graphs that admit perfect state transfer

Sho Kubota, Hiroto Sekido, Harunobu Yata +1 more

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 $K_{2,2}$ and the complete tripartite graph $K_{2,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, [\frac{k}{2}]^α, [0]^β, [-\frac{k}{2}]^γ\}$ , 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.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 $K_{2,2}$ and the complete tripartite graph $K_{2,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, [\frac{k}{2}]^α, [0]^β, [-\frac{k}{2}]^γ\}$, 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.

arXiv:2506.02530Jun 3, 20250 citations

Quantum walks and graph operations

Joy Cooper, Homer De Vera, Hermie Monterde +3 more

Let $U_X(t)$ be the transition matrix of a quantum walk on a graph $X$ relative to its adjacency matrix $A$ or the Laplacian matrix $L$ . This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for $f_{u,v}(t)=\big|U_{X^c}(t)_{u,v}-e^{itδ}U_X(-t)_{u,v}\big|$ and $g_{u,v}(t)=\big||U_X(t)_{u,v}|-|U_{X^c}(t)_{u,v}|\big|$ , where $δ=-1$ when dealing with $A$ and $δ=n$ otherwise. Note that $f_{u,v}(t)$ and $g_{u,v}(t)$ both measure the difference between the behavior of quantum state transfer between vertices $u$ and $v$ in a graph and its complement. If $X$ is regular or $M=L$ , then $f_{u,v}(t)$ is bounded above by $\frac{2}{|V(X)|}$ . If $X$ is non-regular and $M=A$ , then we utilize the main eigenvalues of a graph to obtain an upper bound for $f_{u,v}(t)$ which depends only on $A$ . We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations $|U_X(t)_{u,v}|+|U_{X^c}(t)_{u,v}|$ and $|U_X(t)_{u,v}|\cdot |U_{X^c}(t)_{u,v}|$ . Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.Let $U_X(t)$ be the transition matrix of a quantum walk on a graph $X$ relative to its adjacency matrix $A$ or the Laplacian matrix $L$. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for $f_{u,v}(t)=\big|U_{X^c}(t)_{u,v}-e^{itδ}U_X(-t)_{u,v}\big|$ and $g_{u,v}(t)=\big||U_X(t)_{u,v}|-|U_{X^c}(t)_{u,v}|\big|$, where $δ=-1$ when dealing with $A$ and $δ=n$ otherwise. Note that $f_{u,v}(t)$ and $g_{u,v}(t)$ both measure the difference between the behavior of quantum state transfer between vertices $u$ and $v$ in a graph and its complement. If $X$ is regular or $M=L$, then $f_{u,v}(t)$ is bounded above by $\frac{2}{|V(X)|}$. If $X$ is non-regular and $M=A$, then we utilize the main eigenvalues of a graph to obtain an upper bound for $f_{u,v}(t)$ which depends only on $A$. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations $|U_X(t)_{u,v}|+|U_{X^c}(t)_{u,v}|$ and $|U_X(t)_{u,v}|\cdot |U_{X^c}(t)_{u,v}|$. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.

arXiv:2610.07673Oct 6, 20260 citations

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^+(U^3)

, 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^+(U^2)

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^+(U^3)

, 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^+(U^2)

for regular graphs and show that

S^+(U^2) = S^+(U)^2 + I

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^+(U^3)

, 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

(5^2,5)

under this matrix and thus provide strongly regular counter-examples to the conjecture.

Let

G

be a strongly regular graph of prime order

p

with connection degree

k \geq 6

. We prove that the \emph{quantum walk characteristic polynomial}

χ_q(G,λ) \coloneqq \det(λI - U_G)

, where

U_G

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

U_G

block-diagonalizes under the discrete Fourier transform over

\Z_p

, yielding

p

blocks

U_G^{(j)}

of size

k \times k

. Second, we prove an explicit formula

χ_q\!\bigl(U_G^{(j)}, λ\bigr) = (λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2} \!\left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k}\,λ+ 1\right),

from which the Fourier coefficient

\widehat{A}_G(j)

is recovered as the unique real part of an eigenvalue of

U_G^{(j)}

distinct from

\pm 1

. Third, the inverse discrete Fourier transform recovers the connection set

S

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).

K_{2,2}

and the complete tripartite graph

K_{2,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, [\frac{k}{2}]^α, [0]^β, [-\frac{k}{2}]^γ\}

, 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.

Let

U_X(t)

be the transition matrix of a quantum walk on a graph

X

relative to its adjacency matrix

A

or the Laplacian matrix

L

. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for

f_{u,v}(t)=\big|U_{X^c}(t)_{u,v}-e^{itδ}U_X(-t)_{u,v}\big|

and

g_{u,v}(t)=\big||U_X(t)_{u,v}|-|U_{X^c}(t)_{u,v}|\big|

, where

δ=-1

when dealing with

A

and

δ=n

otherwise. Note that

f_{u,v}(t)

and

g_{u,v}(t)

both measure the difference between the behavior of quantum state transfer between vertices

u

and

v

in a graph and its complement. If

X

is regular or

M=L

, then

f_{u,v}(t)

is bounded above by

\frac{2}{|V(X)|}

. If

X

is non-regular and

M=A

, then we utilize the main eigenvalues of a graph to obtain an upper bound for

f_{u,v}(t)

which depends only on

A

. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations

|U_X(t)_{u,v}|+|U_{X^c}(t)_{u,v}|

and

|U_X(t)_{u,v}|\cdot |U_{X^c}(t)_{u,v}|

. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.