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

A note on the discrete-time evolutions of quantum walk on a graph

Yusuke Higuchi, Norio Konno, Iwao Sato, Etsuo Segawa

Published Jul 20, 2012• 13 citations
arXivHTMLPDF

Abstract

For a quantum walk on a graph, there exist many kinds of operators for the discrete-time evolution. We give a general relation between the characteristic polynomial of the evolution matrix of a quantum walk on edges and that of a kind of transition matrix of a classical random walk on vertices. Furthermore we determine the structure of the positive support of the cube of some evolution matrix, which is said to be useful for isospectral problem in graphs, under a certain condition.

DOI
10.48550/arxiv.1207.4987

Related papers

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

Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs

I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is

•Jan 1, 2009•11 citations

A Characteristic Polynomial for the Transition Probability Matrix of Correlated Random Walks on a Graph

Takashi Komatsu, Norio Konno, Iwao Sato

We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As an application, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.

The Electronic Journal of Combinatorics•Nov 5, 2021•3 citations

A Characteristic Polynomial for The Transition Probability Matrix of A Correlated Random Walk on A Graph

Komatsu, Takashi, Norio Konno, Iwao Sato

We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.

arXiv:2012.09619•Dec 17, 2020•0 citations

Discrete-time semiclassical Szegedy quantum walks

Sergio A. Ortega, Miguel Angel Martin-Delgado

Quantum walks are promising tools based on classical random walks, with plenty of applications such as many variants of optimization. Here we introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. Specifically, a semiclassical walk can be understood as a classical walk where the transition matrix encodes the quantum evolution. We have applied this algorithm to Szegedy’s quantum walk, which can be applied to any arbitrary weighted graph. We first have solved the problem analytically on regular 1D cycles to show the performance of the semiclassical walks. Next, we have simulated our algorithm in a general inhomogeneous symmetric graph, finding that the inhomogeneity drives a symmetry breaking on the graph. Moreover, we show that this phenomenon is useful for the problem of ranking nodes in symmetric graphs, where the classical PageRank fails. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.

arXiv:2303.18202•Physica A Statistical Mechanics and its Applications•Jul 8, 2023•5 citations

Percolated quantum walks with a general shift operator: From trapping to transport

Jan Mareš, Jaroslav Novotný, Igor Jex

We present an alternative definition of discrete-time coined quantum walks convenient for capturing a rather broad spectrum of a walker's behavior on arbitrary graphs. It includes and covers both the geometry of possible walker's positions with interconnecting links and the prescribed rule in which directions the walker will move at each vertex. While the former allows for the analysis of inhomogeneous quantum walks on graphs with vertices of varying degree, the latter offers us to choose, investigate, and compare quantum walks with different shift operators. The synthesis of both key ingredients constitutes a well-suited playground for analyzing percolated quantum walks on a quite general class of graphs. Analytical treatment of the asymptotic behavior of percolated quantum walks is presented and worked out in details for the Grover walk on graphs with maximal degree 3. We find that for these walks with cyclic shift operators, the existence of an edge-3 coloring of the graph allows for nonstationary asymptotic behavior of the walk. For different shift operators, the general structure of localized attractors is investigated, which determines the overall efficiency of a source-to-sink quantum transport across a dynamically changing medium. As a simple nontrivial example of the theory, we treat a single-excitation transport on a percolated cube.

arXiv:1812.02519•Physical Review A•Apr 30, 2019•12 citations
For a quantum walk on a graph, there exist many kinds of operators for the discrete-time evolution. We give a general relation between the characteristic polynomial of the evolution matrix of a quantum walk on edges and that of a kind of transition matrix of a classical random walk on vertices. Furthermore we determine the structure of the positive support of the cube of some evolution matrix, which is said to be useful for isospectral problem in graphs, under a certain condition.
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.
I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph GGG, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of GGG. As an application, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph GGG, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of GGG. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
Quantum walks are promising tools based on classical random walks, with plenty of applications such as many variants of optimization. Here we introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. Specifically, a semiclassical walk can be understood as a classical walk where the transition matrix encodes the quantum evolution. We have applied this algorithm to Szegedy’s quantum walk, which can be applied to any arbitrary weighted graph. We first have solved the problem analytically on regular 1D cycles to show the performance of the semiclassical walks. Next, we have simulated our algorithm in a general inhomogeneous symmetric graph, finding that the inhomogeneity drives a symmetry breaking on the graph. Moreover, we show that this phenomenon is useful for the problem of ranking nodes in symmetric graphs, where the classical PageRank fails. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.
We present an alternative definition of discrete-time coined quantum walks convenient for capturing a rather broad spectrum of a walker's behavior on arbitrary graphs. It includes and covers both the geometry of possible walker's positions with interconnecting links and the prescribed rule in which directions the walker will move at each vertex. While the former allows for the analysis of inhomogeneous quantum walks on graphs with vertices of varying degree, the latter offers us to choose, investigate, and compare quantum walks with different shift operators. The synthesis of both key ingredients constitutes a well-suited playground for analyzing percolated quantum walks on a quite general class of graphs. Analytical treatment of the asymptotic behavior of percolated quantum walks is presented and worked out in details for the Grover walk on graphs with maximal degree 3. We find that for these walks with cyclic shift operators, the existence of an edge-3 coloring of the graph allows for nonstationary asymptotic behavior of the walk. For different shift operators, the general structure of localized attractors is investigated, which determines the overall efficiency of a source-to-sink quantum transport across a dynamically changing medium. As a simple nontrivial example of the theory, we treat a single-excitation transport on a percolated cube.