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:0710.5813 · International Journal of Quantum Information

STUDY OF CONTINUOUS-TIME QUANTUM WALKS ON QUOTIENT GRAPHS VIA QUANTUM PROBABILITY THEORY

S. Salimi

Published Aug 1, 2008• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1142/s0219749908004171

Related papers

CONTINUOUS TIME QUANTUM WALKS AND QUOTIENT GRAPHS

Rahime Sufiani, S. Nami, Mohammad Hassan Golmohammadi +1 more

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.

International Journal of Quantum Information•Apr 1, 2011•1 citation

INVESTIGATION OF CONTINUOUS-TIME QUANTUM WALKS VIA SPECTRAL ANALYSIS AND LAPLACE TRANSFORM

M. A. Jafarizadeh, Rahime Sufiani

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.

arXiv:0704.2602•International Journal of Quantum Information•Aug 1, 2007•16 citations

Quantum walks on quotient graphs

Hari Krovi, Todd A. Brun

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.

arXiv:quant-ph/0701173•Physical Review A•Jun 27, 2007•75 citations

The continuous-time quantum walk on some graphs based on the view of quantum probability

Qi Han, Yaxin Kou, Ning Bai +1 more

In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard [Formula: see text] as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution [Formula: see text] of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, [Formula: see text]-ary tree and [Formula: see text]-fold star power [Formula: see text]. Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained.

International Journal of Quantum Information•Apr 29, 2022•6 citations

CONTINUOUS-TIME QUANTUM WALKS ON TREES IN QUANTUM PROBABILITY THEORY

Norio Konno

A quantum central limit theorem for a continuous-time quantum walk on a homogeneous tree is derived from quantum probability theory. As a consequence, a new type of limit theorems for another continuous-time walk introduced by the walk is presented. The limit density is similar to that given by a continuous-time quantum walk on the one-dimensional lattice.

arXiv:quant-ph/0602213•Infinite Dimensional Analysis Quantum Probability and Related Topics•Jun 1, 2006•45 citations

Continuous-time quantum walks on star graphs

S. Salimi

In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for N-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on K2 graphs (complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.

•Jan 1, 2009•23 citations
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.
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.
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.
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 HHH 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 HHH used to construct it. The quotient graph is constructed by removing the symmetries of the subgroup HHH 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.
In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard [Formula: see text] as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution [Formula: see text] of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, [Formula: see text]-ary tree and [Formula: see text]-fold star power [Formula: see text]. Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained.