Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1603.07666 · Physical Review A

Quantum walks with a one-dimensional coin

Alessandro Bisio, Giacomo Mauro D’Ariano, Marco Erba, Paolo Perinotti, Alessandro Tosini

Published Jun 24, 2016• 21 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.93.062334

Related papers

Chirality from quantum walks without a quantum coin

Giacomo Mauro D’Ariano, Marco Erba, Paolo Perinotti

Quantum walks (QWs) describe the evolution of quantum systems on graphs. An intrinsic degree of freedom---called the coin and represented by a finite-dimensional Hilbert space---is associated with each node. Scalar quantum walks are QWs with a one-dimensional coin. We propose a general strategy allowing one to construct scalar QWs on a broad variety of graphs, which admit embedding in Eulidean spaces, thus having a direct geometric interpretation. After reviewing the technique that allows one to regroup cells of nodes into new nodes, transforming finite spatial blocks into internal degrees of freedom, we prove that no QW with a two-dimensional coin can be derived from an isotropic scalar QW in this way. Finally, we show that the Weyl and Dirac QWs can be derived from scalar QWs in spaces of dimension up to three, via our construction.

arXiv:1902.10227•Physical Review A•Jul 8, 2019•6 citations

Internal degrees of freedom from quantum walks without quantum coin

Giacomo Mauro D’Ariano, Marco Erba, Paolo Perinotti

Quantum walks (QWs) describe the evolution of quantum systems on graphs. An intrinsic degree of freedom---called the coin and represented by a finite-dimensional Hilbert space---is associated to each node. Scalar quantum walks are QWs with a one-dimensional coin. We propose a general strategy allowing one to construct scalar QWs on a broad variety of graphs, which admit embedding in Eulidean spaces, thus having a direct geometric interpretation. After reviewing the technique that allows one to regroup cells of nodes into new nodes, transforming finite spatial blocks into internal degrees of freedom, we prove that no QW with a two-dimensional coin can be derived from an isotropic scalar QW in this way. Finally we show that the Weyl and Dirac QWs can be derived from scalar QWs in spaces of dimension up to three, via our construction.

•Feb 26, 2019•0 citations

Exploring scalar quantum walks on Cayley graphs

Oscar L. Acevedo, Jérémie Roland, Nicolas J. Cerf

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.

arXiv:quant-ph/0609234•Quantum Information and Computation•Jan 1, 2008•6 citations

Virtually Abelian quantum walks

Giacomo Mauro D’Ariano, Marco Erba, Paolo Perinotti +1 more

Abstract We study discrete-time quantum walks on Cayley graphs of non-Abelian groups, focusing on the easiest case of virtually Abelian groups. We present a technique to reduce the quantum walk to an equivalent one on an Abelian group with coin system having larger dimension. This method allows one to extend the notion of wave-vector to the virtually Abelian case and study analytically the walk dynamics. We apply the technique in the case of two quantum walks on virtually Abelian groups with planar Cayley graphs, finding the exact solution in terms of dispersion relation.

arXiv:1511.03992•Journal of Physics A Mathematical and Theoretical•Dec 9, 2016•10 citations

Quantum walks on Cayley graphs

Olga Lopez‐Acevedo, Thierry Gobron

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.

arXiv:quant-ph/0503078•Journal of Physics A Mathematical and General•Dec 21, 2005•27 citations

Quantum random walks on d-regular graphs with Haar-random coin operators

Alice C. Quillen

With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.

quant-pharXiv:2607.04584•Physical Review A•Jul 7, 2026•0 citations
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 GGG. In the literature, investigations concerning infinite GGG have been focused on graphs corresponding to G=ZdG={\mathbb{Z}}^{d}G=Zd with a coin system of dimension 2, whereas for a one-dimensional coin (so-called scalar QWs) only the case of finite GGG has been studied. Here we prove that the evolution of a scalar QW with GGG infinite Abelian is trivial, providing a thorough classification of this kind of walks. Then we consider the infinite dihedral group D\ensuremath∞{D}_{\ensuremath{\infty}}D\ensuremath∞​, that is, the unique non-Abelian group GGG containing a subgroup H\ensuremath≅ZH\ensuremath{\cong}\mathbb{Z}H\ensuremath≅Z with two cosets. We characterize the class of QWs on the Cayley graphs of D\ensuremath∞{D}_{\ensuremath{\infty}}D\ensuremath∞​, and, via a coarse-graining technique, we show that it coincides with the class of spinorial walks on Z\mathbb{Z}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 the evolution of quantum systems on graphs. An intrinsic degree of freedom---called the coin and represented by a finite-dimensional Hilbert space---is associated with each node. Scalar quantum walks are QWs with a one-dimensional coin. We propose a general strategy allowing one to construct scalar QWs on a broad variety of graphs, which admit embedding in Eulidean spaces, thus having a direct geometric interpretation. After reviewing the technique that allows one to regroup cells of nodes into new nodes, transforming finite spatial blocks into internal degrees of freedom, we prove that no QW with a two-dimensional coin can be derived from an isotropic scalar QW in this way. Finally, we show that the Weyl and Dirac QWs can be derived from scalar QWs in spaces of dimension up to three, via our construction.
Quantum walks (QWs) describe the evolution of quantum systems on graphs. An intrinsic degree of freedom---called the coin and represented by a finite-dimensional Hilbert space---is associated to each node. Scalar quantum walks are QWs with a one-dimensional coin. We propose a general strategy allowing one to construct scalar QWs on a broad variety of graphs, which admit embedding in Eulidean spaces, thus having a direct geometric interpretation. After reviewing the technique that allows one to regroup cells of nodes into new nodes, transforming finite spatial blocks into internal degrees of freedom, we prove that no QW with a two-dimensional coin can be derived from an isotropic scalar QW in this way. Finally we show that the Weyl and Dirac QWs can be derived from scalar QWs in spaces of dimension up to three, via our construction.
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.
Abstract We study discrete-time quantum walks on Cayley graphs of non-Abelian groups, focusing on the easiest case of virtually Abelian groups. We present a technique to reduce the quantum walk to an equivalent one on an Abelian group with coin system having larger dimension. This method allows one to extend the notion of wave-vector to the virtually Abelian case and study analytically the walk dynamics. We apply the technique in the case of two quantum walks on virtually Abelian groups with planar Cayley graphs, finding the exact solution in terms of dispersion relation.
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.
With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.