Continuous-time quantum walks (CTQW) over finite group schemes is investigated, where it is shown that some properties of a CTQW over a group scheme defined on a finite group G induces a CTQW over group scheme defined on G/H, where H is a normal subgroup of G with prime index. This reduction can be helpful in analyzing CTQW on underlying graphs of group schemes. Even though this claim is proved for normal subgroups with prime index (using the Clifford's theorem from representation theory), it is checked in some examples that for other normal subgroups or even non-normal subgroups, the result is also true! It means that CTQW over the graph on G, starting from any arbitrary vertex, is isomorphic to the CTQW over the quotient graph on G/H if we take the sum of the amplitudes corresponding to the vertices belonging to the same cosets.
In the present paper, we study the continuous-time quantum walk on quotient graphs. On such graphs, there is a straightforward reduction of the problem to a subspace that can be considerably smaller than the original one. Along the lines of reductions, by using the idea of calculation of the probability amplitudes for continuous-time quantum walk in terms of the spectral distribution associated with the adjacency matrix of graphs [Jafarizadeh and Salimi (Ann. Phys.322 (2007))], we show that the continuous-time quantum walk on original graph Γ induces a continuous-time quantum walk on quotient graph ΓH. Finally, for example, we investigate the continuous-time quantum walk on some quotient Cayley graphs.
A discrete-time quantum walk on a graph $\ensuremath{\Gamma}$ is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. If this unitary evolution operator has an associated group of symmetries, then for certain initial states the walk will be confined to a subspace of the original Hilbert space. Symmetries of the original graph, given by its automorphism group, can be inherited by the evolution operator. We show that a quantum walk confined to the subspace corresponding to this symmetry group can be seen as a different quantum walk on a smaller quotient graph. We give an explicit construction of the quotient graph for any subgroup
H of the automorphism group and illustrate it with examples. The automorphisms of the quotient graph which are inherited from the original graph are the original automorphism group modulo the subgroup
H used to construct it. The quotient graph is constructed by removing the symmetries of the subgroup
H from the original graph. We then analyze the behavior of hitting times on quotient graphs. Hitting time is the average time it takes a walk to reach a given final vertex from a given initial vertex. It has been shown in earlier work [Phys. Rev. A 74, 042334 (2006)] that the hitting time for certain initial states of a quantum walks can be infinite, in contrast to classical random walks. We give a condition which determines whether the quotient graph has infinite hitting times given that they exist in the original graph. We apply this condition for the examples discussed and determine which quotient graphs have infinite hitting times. All known examples of quantum walks with hitting times which are short compared to classical random walks correspond to systems with quotient graphs much smaller than the original graph; we conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speedup.
The continuous-time quantum walk on the underlying graphs of association schemes has been studied, via the algebraic combinatorics structures of association schemes, namely semi-simple modules of their Bose–Mesner and Terwilliger algebras. It is shown that the Terwilliger algebra stratifies the graph into a ( d + 1) disjoint union of strata which is different from the stratification based on distance, except for distance regular graphs. In underlying graphs of association schemes, the probability amplitudes and average probabilities are given in terms of dual eigenvalues of association schemes, such that the amplitudes of observing the continuous-time quantum walk on all sites belonging to a given stratum are the same, therefore there are at most ( d + 1) different observing probabilities. The importance of association scheme in continuous-time quantum walk is shown by some worked out examples such as arbitrary finite group association schemes followed by symmetric S n , Dihedral D 2 m and cyclic groups. At the end it is shown that the highest irreducible representations of Terwilliger algebras pave the way to use the spectral distributions method of Jafarizadeh and Salimi (2005 Preprint quant-ph/0510174) in studying quantum walk on some rather important graphs called distance regular graphs.
Continuous-time quantum walk (CTQW) on a given graph is investigated using the techniques of the spectral analysis and inverse Laplace transform of the Stieltjes function (Stieltjes transform of the spectral distribution) associated with the graph. It is shown that the probability amplitude of observing the CTQW at a given site at time t is related to the inverse Laplace transformation of the Stieltjes function, namely, one can calculate the probability amplitudes only by taking the inverse laplace transform of the function iGμ(is), where Gμ(x) is the Stieltjes function of the graph. The preference of this procedure is that there is no need to know the spectrum of the graph.
Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and
A corresponds to the adjacency matrix of a graph). Our result is, for a
d-sparse graph with
N vertices and evolution time
t, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance,
d=O(1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian
H can be represented as the sum of some Hamiltonians
Hj, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.
In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.