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={\mathbb{Z}}^{d}$ 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 $\mathbb{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.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={\mathbb{Z}}^{d}$ 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 $\mathbb{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.

arXiv:1603.07666Physical Review AJun 24, 201621 citations

Quantum Walks on Finite Graphs

Renato Portugal

Springer eBooksJan 1, 20130 citations

Open quantum walks on graphs

Stéphane Attal, Francesco Petruccione, Ilya Sinayskiy

arXiv:1401.3305Physics Letters AMar 21, 201271 citations

Quantum walks with infinite hitting times

Hari Krovi, Todd A. Brun

Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.

arXiv:quant-ph/0606094Physical Review AOct 27, 200687 citations

Symmetry in quantum walks

Todd A. Brun, Hari Krovi

A discrete-time quantum walk on a graph is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. We derive an expression for hitting time using superoperators, and numerically evaluate it for the walk on the hypercube for various coins and decoherence models. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Symmetries of a graph, given by its automorphism group, can be inherited by the evolution operator. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. Symmetry can cause the walk to also be confined to a subspace of the original Hilbert space for cartain initial states. 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. 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. We conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speed-up. Finally, we use symmetry and the theory of decoherence-free subspaces to determine when the subspace of the quotient graph is a decoherence-free subspace of the dynamics.A discrete-time quantum walk on a graph is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. We derive an expression for hitting time using superoperators, and numerically evaluate it for the walk on the hypercube for various coins and decoherence models. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Symmetries of a graph, given by its automorphism group, can be inherited by the evolution operator. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. Symmetry can cause the walk to also be confined to a subspace of the original Hilbert space for cartain initial states. 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. 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. We conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speed-up. Finally, we use symmetry and the theory of decoherence-free subspaces to determine when the subspace of the quotient graph is a decoherence-free subspace of the dynamics.

Jan 1, 20077 citations

G

. In the literature, investigations concerning infinite

G

have been focused on graphs corresponding to

G={\mathbb{Z}}^{d}

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

\mathbb{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.