| dc.description.abstract | We study a discrete quantum walk model called bipartite walks via a spectral approach. A bipartite walk is determined by a unitary matrix U, i.e., the transition matrix of the walk. For every transition matrix U, there is a Hamiltonian H such that U = exp(iH). If there is a real skew-symmetric matrix S such that H = iS, we say there is a H-digraph associated to the walk and S is the skew-adjacency matrix of the H-digraph. The underlying unweighted non-oriented graph of the H-digraph is H-graph. Let G be a
simple bipartite graph with no isolated vertices. The bipartite walk on G is the same as the continuous walk on the H-digraph over integer time. Two questions lie in the centre of this thesis are
1. Is there a connection between the H-(di)graph and the underlying
graph G? If there is, what is the connection?
2. Is there a connection between the walk and the underlying graph G?
If there is, what is the connection?
Given a bipartite walk on G, we show that the underlying bipartite
graph G determines the existence of the H-graph. If G is biregular, the
spectrum of G determines the spectrum of U.
We give complete characterizations of bipartite walks on paths and even
cycles. Given a path or an even cycle, the transition matrix of the bipartite
walk is a permutation matrix. The H-digraph is an oriented weighted complete
graph. Using bipartite walks on even paths, we construct a in nite
family of oriented weighted complete graphs such that continuous walks de-
ned on them have universal perfect state transfer, which is an interesting
but rare phenomenon.
Grover's walk is one of the most studied discrete quantum walk model
and it can be used to implement the famous Grover's algorithm. We show
that Grover's walk is actually a special case of bipartite walks. Moreover,
given a bipartite graph G, one step of the bipartite walk on G is the same
as two steps of Grover's walk on the same graph.
We also study periodic bipartite walks. Using results from algebraic
number theory, we give a characterization of periodic walks on a biregular
graph with a constraint on its spectrum. This characterization only depends
on the spectrum of the underlying graph and the possible spectrum for a
periodic walk is determined by the degrees of the underlying graph. We apply this characterization of periodic bipartite walk to Grover's walk to
get a characterization of a certain class of periodic Grover's walk.
Lastly, we look into bipartite walks on the incidence graphs of incidence
structures, t-designs (t 2) and generalized quadrangles in particular.
Given a bipartite walk on a t-design, we show that if the underlying
design is a partial linear space, the H-graph is the distance-two graph of the
line graph of the underlying incidence graph. Given a bipartite walk on the
incidence graph of a generalized quadrangle, we show that there is a homogeneous
coherent algebra raised from the bipartite walk. This homogeneous
coherent algebra is useful in analyzing the behavior of the walk. | en |
