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:1703.01334 · Journal of Physics A Mathematical and Theoretical

Quantum walks induced by Dirichlet random walks on infinite trees

Yusuke Higuchi, Etsuo Segawa

Published Jan 19, 2018• 17 citations
arXivHTMLPDF

Abstract

Abstract We consider the Grover walk on infinite trees from the viewpoint of spectral analysis. From the previous work, infinite regular trees provide localization. In this paper, we give the complete characterization of the eigenspace of this Grover walk, which involves localization of its behavior and recovers the previous work. Our result suggests that the Grover walk on infinite trees may be regarded as a limit of the quantum walk induced by the isotropic random walk with the Dirichlet boundary condition at the n -th depth rather than one with the Neumann boundary condition.

DOI
10.1088/1751-8121/aa8fba

Related papers

Localization of quantum walks on a deterministic recursive tree

X. P. Xu

Localization of quantum walks can be characterized by the return probability, i.e., the probability for the walker returning to its original site. In this paper, we consider localization of continuous-time quantum walks in terms of return probability on a deterministic recursive tree, which is generated by adding one node and connecting it to each node of the existing tree recursively. We obtain an approximate form for the return probability using the complete eigenvalues and eigenstates of Laplace matrix of the structure. It is found that the return probability depends on the initial node of the excitation. When the walk starts at the central nodes, the return probability converges to a constant value even in the limit of infinite system, in contrast to an exponential decay of the return probability if the walk starts at the outlying nodes. We also observe a bipartite structure for the distribution of return probability, and provide theoretical interpretation for all our findings. Our results suggest that quantum walks display significant localization and well-bedded structure of return probability on heterogeneous trees.

Quantum Information and Computation•Mar 1, 2011•3 citations

Relation between Quantum Walks with Tails and Quantum Walks with Sinks on Finite Graphs

Norio Konno, Etsuo Segawa, M. Štefaňák

We connect the Grover walk with sinks to the Grover walk with tails. The survival probability of the Grover walk with sinks in the long time limit is characterized by the centered generalized eigenspace of the Grover walk with tails. The centered eigenspace of the Grover walk is the attractor eigenspace of the Grover walk with sinks. It is described by the persistent eigenspace of the underlying random walk whose support has no overlap to the boundaries of the graph and combinatorial flow in graph theory.

arXiv:2105.03111•Symmetry•Jun 29, 2021•5 citations

Spectral and asymptotic properties of Grover walks on crystal lattice

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

We propose a twisted Szegedy walk for estimating the limit behavior of a discrete-time quantum walk on a crystal lattice, an infinite abelian covering graph, whose notion was introduced by [14]. First, we show that the spectrum of the twisted Szegedy walk on the quotient graph can be expressed by mapping the spectrum of a twisted random walk onto the unit circle. Secondly, we show that the spatial Fourier transform of the twisted Szegedy walk on a finite graph with appropriate parameters becomes the Grover walk on its infinite abelian covering graph. Finally, as an application, we show that if the Betti number of the quotient graph is strictly greater than one, then localization is ensured with some appropriated initial state. We also compute the limit density function for the Grover walk on $\mathbb{Z}^d$ with flip flop shift, which implies the coexistence of linear spreading and localization. We partially obtain the abstractive shape of the limit density function: the support is within the $d$-dimensional sphere of radius $1/\sqrt{d}$, and $2^d$ singular points reside on the sphere's surface.

arXiv:1401.0154•Dec 31, 2013•2 citations

Localization of discrete time quantum walks on the glued trees

Yusuke Ide, Norio Konno, Etsuo Segawa +1 more

In this paper, we consider the time averaged distribution of discrete time quantum walks on the glued trees. In order to analyse the walks on the glued trees, we consider a reduction to the walks on path graphs. Using a spectral analysis of the Jacobi matrices defined by the corresponding random walks on the path graphs, we have spectral decomposition of the time evolution operator of the quantum walks. We find significant contributions of the eigenvalues $\pm 1$ of the Jacobi matrices to the time averaged limit distribution of the quantum walks. As a consequence we obtain lower bounds of the time averaged distribution.

•Aug 16, 2016•8 citations

Localization of Discrete Time Quantum Walks on the Glued Trees

Yusuke Ide, Norio Konno, Etsuo Segawa +1 more

In this paper, we consider the time averaged distribution of discrete time quantum walks on the glued trees. In order to analyze the walks on the glued trees, we consider a reduction to the walks on path graphs. Using a spectral analysis of the Jacobi matrices defined by the corresponding random walks on the path graphs, we have a spectral decomposition of the time evolution operator of the quantum walks. We find significant contributions of the eigenvalues, ±1, of the Jacobi matrices to the time averaged limit distribution of the quantum walks. As a consequence, we obtain the lower bounds of the time averaged distribution.

arXiv:1312.1149•Entropy•Mar 18, 2014•9 citations

Spreading behavior of quantum walks induced by random walks

Yusuke Higuchi, Etsuo Segawa

In this paper, we consider the quantum walk on Z with attachment of one-length path periodically. This small modification to Z provides localization of the quantum walk. The eigenspace causing this localization is generated by finite length round trip paths. We find that the localization is due to the eigenvalues of an underlying random walk. Moreover we find that the transience of the underlying random walk provides a slow down of the pseudo velocity of the induced quantum walk and a different limit distribution from the Konno distribution.

Quantum Information and Computation•Apr 1, 2017•9 citations
Abstract We consider the Grover walk on infinite trees from the viewpoint of spectral analysis. From the previous work, infinite regular trees provide localization. In this paper, we give the complete characterization of the eigenspace of this Grover walk, which involves localization of its behavior and recovers the previous work. Our result suggests that the Grover walk on infinite trees may be regarded as a limit of the quantum walk induced by the isotropic random walk with the Dirichlet boundary condition at the n -th depth rather than one with the Neumann boundary condition.
Localization of quantum walks can be characterized by the return probability, i.e., the probability for the walker returning to its original site. In this paper, we consider localization of continuous-time quantum walks in terms of return probability on a deterministic recursive tree, which is generated by adding one node and connecting it to each node of the existing tree recursively. We obtain an approximate form for the return probability using the complete eigenvalues and eigenstates of Laplace matrix of the structure. It is found that the return probability depends on the initial node of the excitation. When the walk starts at the central nodes, the return probability converges to a constant value even in the limit of infinite system, in contrast to an exponential decay of the return probability if the walk starts at the outlying nodes. We also observe a bipartite structure for the distribution of return probability, and provide theoretical interpretation for all our findings. Our results suggest that quantum walks display significant localization and well-bedded structure of return probability on heterogeneous trees.
We connect the Grover walk with sinks to the Grover walk with tails. The survival probability of the Grover walk with sinks in the long time limit is characterized by the centered generalized eigenspace of the Grover walk with tails. The centered eigenspace of the Grover walk is the attractor eigenspace of the Grover walk with sinks. It is described by the persistent eigenspace of the underlying random walk whose support has no overlap to the boundaries of the graph and combinatorial flow in graph theory.
We propose a twisted Szegedy walk for estimating the limit behavior of a discrete-time quantum walk on a crystal lattice, an infinite abelian covering graph, whose notion was introduced by [14]. First, we show that the spectrum of the twisted Szegedy walk on the quotient graph can be expressed by mapping the spectrum of a twisted random walk onto the unit circle. Secondly, we show that the spatial Fourier transform of the twisted Szegedy walk on a finite graph with appropriate parameters becomes the Grover walk on its infinite abelian covering graph. Finally, as an application, we show that if the Betti number of the quotient graph is strictly greater than one, then localization is ensured with some appropriated initial state. We also compute the limit density function for the Grover walk on Zd\mathbb{Z}^dZd with flip flop shift, which implies the coexistence of linear spreading and localization. We partially obtain the abstractive shape of the limit density function: the support is within the ddd-dimensional sphere of radius 1/d1/\sqrt{d}1/d​, and 2d2^d2d singular points reside on the sphere's surface.
In this paper, we consider the time averaged distribution of discrete time quantum walks on the glued trees. In order to analyse the walks on the glued trees, we consider a reduction to the walks on path graphs. Using a spectral analysis of the Jacobi matrices defined by the corresponding random walks on the path graphs, we have spectral decomposition of the time evolution operator of the quantum walks. We find significant contributions of the eigenvalues ±1\pm 1±1 of the Jacobi matrices to the time averaged limit distribution of the quantum walks. As a consequence we obtain lower bounds of the time averaged distribution.
In this paper, we consider the time averaged distribution of discrete time quantum walks on the glued trees. In order to analyze the walks on the glued trees, we consider a reduction to the walks on path graphs. Using a spectral analysis of the Jacobi matrices defined by the corresponding random walks on the path graphs, we have a spectral decomposition of the time evolution operator of the quantum walks. We find significant contributions of the eigenvalues, ±1, of the Jacobi matrices to the time averaged limit distribution of the quantum walks. As a consequence, we obtain the lower bounds of the time averaged distribution.
In this paper, we consider the quantum walk on Z with attachment of one-length path periodically. This small modification to Z provides localization of the quantum walk. The eigenspace causing this localization is generated by finite length round trip paths. We find that the localization is due to the eigenvalues of an underlying random walk. Moreover we find that the transience of the underlying random walk provides a slow down of the pseudo velocity of the induced quantum walk and a different limit distribution from the Konno distribution.