We address the problem of the construction of quantum walks on Cayley graphs. Our main motivation is the relationship between quantum algorithms and quantum walks. In particular, we discuss the choice of the dimension of the local Hilbert space and consider various classes of graphs on which the structure of quantum walks may differ. We completely characterize quantum walks on free groups and present partial results on more general cases. Some examples are given including a family of quantum walks on the hypercube involving a Clifford algebra.
A quantum walk, \emph{i.e.}, the quantum evolution of a particle on a graph, is termed \emph{scalar} if the internal space of the moving particle (often called the coin) has dimension one. Here, we study the existence of scalar quantum walks on Cayley graphs, which are built from the generators of a group. After deriving a necessary condition on these generators for the existence of a scalar quantum walk, we present a general method to express the evolution operator of the walk, assuming homogeneity of the evolution. We use this necessary condition and the subsequent constructive method to investigate the existence of scalar quantum walks on Cayley graphs of groups presented with two or three generators. In this restricted framework, we classify all groups -- in terms of relations between their generators -- that admit scalar quantum walks, and we also derive the form of the most general evolution operator. Finally, we point out some interesting special cases, and extend our study to a few examples of Cayley graphs built with more than three generators.
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.
Quantum walks (QWs) describe particles evolving coherently on a graph. The internal degree of freedom corresponds to a Hilbert space, called a coin system. We consider QWs on Cayley graphs of some group
G. In the literature, investigations concerning infinite
G have been focused on graphs corresponding to
G=Zd with a coin system of dimension 2, whereas for a one-dimensional coin (so-called scalar QWs) only the case of finite
G has been studied. Here we prove that the evolution of a scalar QW with
G infinite Abelian is trivial, providing a thorough classification of this kind of walks. Then we consider the infinite dihedral group ${D}_{\ensuremath{\infty}}$, that is, the unique non-Abelian group
G containing a subgroup $H\ensuremath{\cong}\mathbb{Z}$ with two cosets. We characterize the class of QWs on the Cayley graphs of ${D}_{\ensuremath{\infty}}$, and, via a coarse-graining technique, we show that it coincides with the class of spinorial walks on
Z which satisfies parity symmetry. This class of QWs includes the Weyl and the Dirac QWs. Remarkably, there exist also spinorial walks that are not coarse graining of a scalar QW, such as the Hadamard walk.
In this paper we isolate the combinatorial property responsible (at least in part) for the computational speedups recently observed in some quantum walk algorithms. We find that continuous-time quantum walks can exploit the covering space property of certain graphs. We demonstrate that a quantum walk on a graph Y which covers a smaller graph X can be equivalent to a quantum walk on the smaller graph X. This equivalence occurs only when the walk begins on certain initial states, fibre-constant states, which respect the graph covering space structure. We illustrate these observations with walks on Cayley graphs; we show that walks on fibre-constant initial states for Cayley graphs are equivalent to walks on the induced Schreier graph. We also consider the problem of constructing efficient gate sequences simulating the time evolution of a continuous-time quantum walk. For the case of the walk on the m-torus graph T^m on 2^n vertices we construct a gate sequence which uses O(\poly(n)) gates which is independent of the time t the walk is simulated for (and so the sequence can simulate the walk for exponential times). We argue that there exists a wide class of nontrivial operators based on quantum walks on graphs which can be measured efficiently. We introduce a new general class of computational problems, HiddenCover, which includes a variant of the general hidden subgroup problem as a subclass. We argue that quantum computers ought to be able to utilise covering space structures to efficiently solve HiddenCover problems.