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:1211.0172

Symmetries in discrete time quantum walks on Cayley graphs

Václav Potoček

Published Nov 1, 2012• 1 citation
arXivHTMLPDF

Abstract

We address the question of symmetries of an important type of quantum walks. We introduce all the necessary definitions and provide a rigorous formulation of the problem. Using a thorough analysis, we reach the complete answer by presenting a constructive method of finding all solutions of the problem with minimal additional assumptions. We apply the results on an example of a quantum walk on a line to demonstrate the practical significance of the theory.

DOI
10.48550/arxiv.1211.0172

Related papers

QUANTUM WALKS ON CAYLEY GRAPHS

O. Lopez, Acevedo, Thierry Gobron

Abstract. 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 characterise 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. PACS number: 03.67.LxQuantum walks on Cayley graphs 2 1.

•Jan 1, 2005•21 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 walks on highly symmetric graphs

Mark S. Hillery

We study discrete-time quantum walks on the complete and bipartite graphs. We show how they can be used to perform searches. The symmetry of these graphs leads to a significant dimensional reduction of the problem.

International Conference on Quantum Information•Jan 1, 2008•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

Quantum Walks on the Line with Phase Parameters

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1 more

In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.

arXiv:1109.1866•IEICE Transactions on Information and Systems•Jan 1, 2012•5 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
We address the question of symmetries of an important type of quantum walks. We introduce all the necessary definitions and provide a rigorous formulation of the problem. Using a thorough analysis, we reach the complete answer by presenting a constructive method of finding all solutions of the problem with minimal additional assumptions. We apply the results on an example of a quantum walk on a line to demonstrate the practical significance of the theory.
Abstract. 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 characterise 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. PACS number: 03.67.LxQuantum walks on Cayley graphs 2 1.
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 this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.
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.