A discrete-time quantum walk is the quantum analogue of a Markov chain on a graph. We show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to study perfect state transfer in a model of discrete-time quantum walk whose transition matrix is given by two reflections, defined by the face and vertex incidence relations of a graph embedded in an orientable surface, proposed by Zhan [ J. Algebraic Combin. 53(4):1187–1213, 2020]. For this model, called the vertex-face walk, we prove results about perfect state transfer and periodicity and give infinite families of examples where these occur. In doing so, we bring together tools from algebraic and topological graph theory to analyze the evolution of this walk.
A discrete-time quantum walk is the quantum analogue of a Markov chain on a graph. We show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to study perfect state transfer in a model of discrete-time quantum walk whose transition matrix is given by two reflections, defined by the face and vertex incidence relations of a graph embedded in an orientable surface, proposed by Zhan [ J. Algebraic Combin. 53(4):1187–1213, 2020]. For this model, called the vertex-face walk, we prove results about perfect state transfer and periodicity and give infinite families of examples where these occur. In doing so, we bring together tools from algebraic and topological graph theory to analyze the evolution of this walk.
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.
In this paper, we analyze state transfer in quantum walks by using combinatorial methods. We generalize perfect state transfer in two-reflection discrete-time quantum walks to a notion that we call peak state transfer; we define peak state transfer as the highest state transfer that can be achieved between an initial and a target state under unitary evolution, even when perfect state transfer is unattainable. We give a spectral characterization of peak state transfer that allows us to fully characterize peak state transfer in the arc-reversal (Grover) walk on various families of graphs, including strongly regular graphs and incidence graphs of block designs (assuming that the walk starts at a point of the design). In addition, we provide many examples of peak state transfer, including an infinite family where the amount of peak state transfer tends to 1 as the number of vertices grows. We further demonstrate that peak state transfer properties extend to infinite families of graphs generated by vertex blow-ups, and we characterize periodicity in the vertex-face walk on toroidal grids. In our analysis, we make extensive use of the spectral decomposition of a matrix that is obtained by projecting the transition matrix down onto a subspace. Though we are motivated by a problem in quantum computing, we identify several open problems that are purely combinatorial, arising from the spectral conditions required for peak state transfer in discrete-time quantum walks.
Given a graph with Hermitian adjacency matrix H, perfect state transfer occurs from vertex a to vertex b if the (b,a)-entry of the unitary matrix exp(−iHt) has unit magnitude for some time t. This phenomenon is relevant for information transmission in quantum spin networks and is known to be monogamous under real symmetric matrices. We prove the following results: 1. For oriented graphs (whose nonzero weights are ±i), the oriented 3-cycle and the oriented edge are the only graphs where perfect state transfer occurs between every pair of vertices. This settles a conjecture of Cameron et al. On the other hand, we construct an infinite family of oriented graphs with perfect state transfer between any pair of vertices on a subset of size four. 2. There are infinite families of Hermitian graphs with one-way perfect state transfer, where perfect state transfer occurs without periodicity. In contrast, perfect state transfer implies periodicity whenever the adjacency matrix has algebraic entries (as shown by Godsil). 3. There are infinite families with non-monogamous pretty good state transfer in rooted graph products. In particular, we generalize known results on double stars (due to Fan and Godsil) and on paths with loops (due to Kempton, Lippner and Yau). The latter extends the experimental observation of quantum transport (made by Zimborás et al.) and shows non-monogamous pretty good state transfer can occur amongst distant vertices.
This thesis extends results about periodicity and perfect state transfer \nto oriented graphs. We prove that if a vertex a is periodic, then elements of \nthe eigenvalue support lie in Z √∆ for some squarefree negative integer \n∆. We find an infinite family of orientations of the complete graph that are \nperiodic. We find an example of a graph with both perfect state transfer \nand periodicity that is not periodic at an integer multiple of the period, and \nwe prove and use Gelfond-Schneider Theorem to show that every oriented \ngraph with perfect state transfer between two vertices will have both vertices \nperiodic. We find a complete characterization of when perfect state transfer \ncan occur in oriented graphs, and find a new example of a graph where one \nvertex has perfect state transfer to multiple other vertices.
Perfect state transfer between two marked vertices of a graph by means of a discrete-time quantum walk is analyzed. We consider the quantum walk search algorithm with two marked vertices, sender and receiver. It is shown by explicit calculation that, for the coined quantum walks on a star graph and a complete graph with self-loops, perfect state transfer between the sender and receiver vertex is achieved for an arbitrary number of vertices N in O(N) steps of the walk. Finally, we show that Szegedy's walk with queries on a complete graph allows for state transfer with unit fidelity in the limit of large N.
Let G be a graph and let t be a positive real number. Then the evolution of the continuous quantum walk defined on G is described by the transition matrix U(t)=exp(itH).The matrix H is called Hamiltonian. So far the most studied quantum walks are the ones whose Hamiltonians are the adjacency matrices of the underlying graphs and initial states are vertex states e_a, with e_a being the characteristic vector of vertex a. \n \nThis thesis focuses on Laplacian edge state transfer, that is, the quantum walks whose initial states are edge states e_a-e_b and Hamiltonians are the Laplacians of the underlying graphs. So far the research about perfect state transfer only involves vertex states and Laplacian edge state transfer has not been studied before. We extend the known results of perfect vertex state transfer and periodicity of vertex states to Laplacian edge state transfer. \n \nWe prove two useful closure properties for perfect Laplacian edge state transfer. One is that complementation preserves perfect edge state transfer. The other is that if G has perfect Laplacian edge state transfer at time τ and H has perfect Laplacian vertex state transfer also at time τ, then with some mild assumption on the pairs of vertex states and edge states that have perfect state transfer, the Cartesian product G □ H also admits perfect edge state transfer. Those two properties provide us new ways to construct graphs with perfect Laplacian edge state transfer. We also observe one phenomenon that happens in Laplacian edge state transfer which never happens in vertex state transfer: if there is perfect state transfer from e_a-e_b to e_α-e_β and also from e_b-e_c to e_β-e_γ at the same time t in G, then G admits perfect state transfer from e_a-e_c to e_α-e_γ at time t. \n \nWe give characterizations of perfect Laplacian edge state transfer in cycles, paths and complete bipartite graphs K_{2,4n}. We study perfect state transfer and periodicity on edge states with special spectral features. We also consider the case when the unsigned Laplacian is Hamiltonian and initial states are plus states of the form e_a+e_b. In this case, we characterize perfect state transfer in paths, cycles and bipartite graphs. \nWe close this thesis by a list of open questions.