Over the last two decades quantum walks have proven to be a very useful concept in quantum information processing, quantum communication and quantum simulations. The presented thesis reviews our contribution to this field of research. We provide a thorough introduction to methods used for the study of quantum walks and their potential applications. To keep the presentation intelligible we focus on specific examples. In particular, we analyze in detail the properties of homogeneous quantum walks on a one-dimensional lattice with two and three internal states. The application of the obtained results is illustrated on the examples persistence of unvisited sites and quantum transport to an absorbing sink. We also discuss quantum walks on finite graphs and their applications to quantum search and perfect state transfer. Extension of the presented results, which can be found in enclosed published papers, is discussed in detail.
Inspired by the classical spectral analysis of birth-death chains using orthogonal polynomials, we study an analogous set of constructions in the context of open quantum dynamics and related walks. In such setting, block tridiagonal matrices and matrix-valued orthogonal polynomials are the natural objects to be considered. We recall the problems of the existence of a matrix of measures or weight matrix together with concrete calculations of basic statistics of the walk, such as site recurrence and first passage time probabilities, with these notions being defined in terms of a quantum trajectories formalism. The discussion concentrates on the models of quantum Markov chains, due to S. Gudder, and on the particular class of open quantum walks, due to S. Attal et al. The folding trick for birth-death chains on the integers is revisited in this setting together with applications of the matrix-valued Stieltjes transform associated with the measures, thus extending recent results on the subject. Finally, we consider the case of non-symmetric weight matrices and explore some examples.
Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum walk in X. We say that X admits perfect state transfer from a vertex u to a vertex v if there is a time t such that \n| exp(i t A)_(u,v) | = 1. \n \nThe main problem we study in this thesis is that of determining which simple graphs admit perfect state transfer. For some classes of graphs the problem is solved. For example, a path on n vertices admits perfect state transfer if and only if n=2 or n=3. However, the general problem of determining all graphs that admit perfect state transfer is substantially hard. \n \nIn this thesis, we focus on some special cases. We provide necessary and sufficient conditions for a distance-regular graph to admit perfect state transfer. In particular, we provide a detailed account of which distance-regular graphs of diameter three do so. \n \nA graph is said to be spectrally extremal if the number of distinct eigenvalues is equal to the diameter plus one. Distance-regular graphs are examples of such graphs. We study perfect state transfer in spectrally extremal graphs and explore rich connections to the topic of orthogonal polynomials. We characterize perfect state transfer in such graphs. \n \nWe also provide a general framework in which perfect state transfer in graph products can be studied. We use this to determine when direct products and double covers of graphs admit perfect state transfer. As a consequence, we provide many new examples of simple graphs admitting perfect state transfer. We also provide some advances in the understanding of perfect state transfer in Cayley graphs for the groups (Z_2)^d and Z_n. \n \nFinally, we consider the problem of determining which trees admit perfect state transfer. We show more generally that, except for the path on two vertices, if a connected bipartite graph contains a unique perfect matching, then it cannot admit perfect state transfer. We also consider this problem in the context of another model of quantum walks determined by the matrix exp(i t L), where L is the Laplacian matrix of the graph. In particular, we show that no tree on an odd number of vertices admits perfect state transfer according to this model.
This paper investigates perfect state transfer (PST) in discrete-time quantum walks constructed via the shunt decomposition method. The walks are defined on a graph
G and its associated quotient graph
G/π, induced by an equitable partition
π. Through the shunt decomposition of
G, we derive an explicit relation between the shift operator of the parent graph
G and that of its quotient graph
G/π. We construct a reflection operator based on the characteristic matrix, which establishes a connection between the transition operator of the parent graph and that of its lower-dimensional quotient graph. We then prove that PST occurs on
G if and only if it occurs on
G/π. Furthermore, we express the unitary evolution operator of the quotient graph in terms of Chebyshev polynomials of the first kind, from which we derive explicit criteria for PST. As an application, we establish PST on the cycle graph
Cn at time
k=n/2, and lift the result to the parent graph
C2n via the equitable partition
π. We further show that if an equitable partition
π of
G induces a quotient isomorphic to
Kn↺, the complete digraph on
n vertices with a loop at every vertex, then PST occurs at step
k=n, and the walk is periodic at
k=2n. This framework is applied to two families of graphs, which are the complete bipartite digraph
Kn,n⇌ and the circulant graph
Circ(2n,S), where
S consists of all odd residues modulo
2n and
n=2s for some
s≥1, establishing PST in their respective line digraphs. Collectively, these results also answer the question posed by Godsil and Zhan concerning which shunt decompositions or embeddings of a graph admit PST.
Abstract Continuous-time quantum walks (CTQW) becoming more significant for quantum information and quantum computation. The perfect state transfer (PST) on graphs is a specific phenomena of CTQW which is widely used in quantum communication of small system, and be found critical for quantum algorithm design recently, such as quantum approximate optimization algorithms and quantum search. If a network
G contains
2N vertices, and PST occurs between
N pairs of vertices at the same time
T, then we say
G admits symmetric PST (SPST). In this work, we will study the SPST on bipartite graphs via spectra. And then, we will present how to set couplings of special bipartite graphs such as cycles, grids and chains to admit SPST is given. For cycles with 6, 8, 10, 12 vertices, we give the analytical method to obtain the couplings to admit SPST. Analogously, the couplings for chains and grids to admit SPST are analytical obtained. We also present a typical approach by using the graph tensor product to construct new quantum networks that admit SPST, in which the new quantum networks are derived from special kinds of integral graphs, such as complete graphs, strongly regular graphs and distance regular graphs.