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:1009.1306 · Quantum Information and Computation

Limit theorems for the discrete-time quantum walk on a graph with joined half lines

Kota Chisaki, Norio Konno, Etsuo Segawa

Published Mar 1, 2012• 12 citations
arXivHTMLPDF

Abstract

We consider a discrete-time quantum walk W_{t,\kappa} at time t on a graph with joined half lines J_\kappa, which is composed of \kappa half lines with the same origin. Our analysis is based on a reduction of the walk on a half line. The idea plays an important role to analyze the walks on some class of graphs with symmetric initial states. In this paper, we introduce a quantum walk with an enlarged basis and show that W_{t,\kappa} can be reduced to the walk on a half line even if the initial state is asymmetric. For W_{t,\kappa}, we obtain two types of limit theorems. The first one is an asymptotic behavior of W_{t,\kappa} which corresponds to localization. For some conditions, we find that the asymptotic behavior oscillates. The second one is the weak convergence theorem for W_{t,\kappa}. On each half line, W_{t,\kappa} converges to a density function like the case of the one-dimensional lattice with a scaling order of t. The results contain the cases of quantum walks starting from the general initial state on a half line with the general coin and homogeneous trees with the Grover coin.

DOI
10.26421/qic12.3-4-10

Related papers

Limit Theorems for Discrete-Time Quantum Walks on Trees

Kota Chisaki, Masatoshi Hamada, Norio Konno +1 more

We consider a discrete-time quantum walk Wt given by the Grover transformation on the homogeneous tree. We reduce Wt to a quantum walk Xt on a half line with a wall at the origin. This paper presents two types of limit theorems for Xt. The first one is Xt as t→∞, which corresponds to a localization in the case of an initial qubit state. The second one is Xt⁄t as t→∞, whose limit density is given by the Konno density function [1–4]. The density appears in various situations of discrete-time cases. The corresponding similar limit theorem was proved in [5] for a continuous-time case on the homogeneous tree.

arXiv:0903.4508•Interdisciplinary Information Sciences•Jan 1, 2009•36 citations

Limit theorems for the discrete-time quantum walk on a graph with joined half lines

ChisakiKota, KonnoNorio, SegawaEtsuo

We consider a discrete-time quantum walk Wt,κ at time t on a graph with joined half lines Jκ, which is composed of κ half lines with the same origin. Our analysis is based on a reduction of the wal...

Quantum Information and Computation•Mar 1, 2012•0 citations

WEAK LIMITS FOR QUANTUM WALKS ON THE HALF-LINE

CHAOBIN LIU, NELSON PETULANTE

For a discrete two-state quantum walk (QW) on the half-line with a general condition at the boundary, we formulate and prove a weak limit theorem describing the terminal behavior of its transition probabilities. In this context, localization is possible even for a walk predicated on the assumption of homogeneity. For the Hadamard walk on the half-line, the weak limit is shown to be independent of the initial coin state and to exhibit no localization.

arXiv:1212.1109•International Journal of Quantum Information•Sep 1, 2013•7 citations

Limit theorems and localization of three-state quantum walks on a line defined by generalized Grover coins

Amrita Mandal, Rohit Sarma Sarkar, Shantanav Chakraborty +1 more

In this article, we undertake a detailed study of the limiting behavior of a three-state discrete-time quantum walk on a one-dimensional lattice with generalized Grover coins. Two limit theorems are proved and consequently we show that the quantum walk exhibits localization at its initial position for a wide range of coin parameters. Finally, we discuss the effect of the coin parameters on the peak velocities of probability distributions of the underlying quantum walks.

arXiv:2204.05625•Physical Review A•Oct 4, 2022•6 citations

Relation between random walks and quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

Based on studies of four specific networks, we conjecture a general relation between the walk dimensions ${d}_{w}$ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that ${d}_{w}$ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\ensuremath{\rho}(x,t)$ in space and time of this quantum-walk equation exhibits a scaling collapse for a variable ${x}^{{d}_{w}}/t$ in the weak limit, which defines ${d}_{w}$ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\ensuremath{\rho}(x,t)$ in each case with extensive numerical simulation. The exact values for ${d}_{w}$ themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.

arXiv:1410.7034•Physical Review A•May 29, 2015•23 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
We consider a discrete-time quantum walk W_{t,\kappa} at time t on a graph with joined half lines J_\kappa, which is composed of \kappa half lines with the same origin. Our analysis is based on a reduction of the walk on a half line. The idea plays an important role to analyze the walks on some class of graphs with symmetric initial states. In this paper, we introduce a quantum walk with an enlarged basis and show that W_{t,\kappa} can be reduced to the walk on a half line even if the initial state is asymmetric. For W_{t,\kappa}, we obtain two types of limit theorems. The first one is an asymptotic behavior of W_{t,\kappa} which corresponds to localization. For some conditions, we find that the asymptotic behavior oscillates. The second one is the weak convergence theorem for W_{t,\kappa}. On each half line, W_{t,\kappa} converges to a density function like the case of the one-dimensional lattice with a scaling order of t. The results contain the cases of quantum walks starting from the general initial state on a half line with the general coin and homogeneous trees with the Grover coin.
We consider a discrete-time quantum walk Wt given by the Grover transformation on the homogeneous tree. We reduce Wt to a quantum walk Xt on a half line with a wall at the origin. This paper presents two types of limit theorems for Xt. The first one is Xt as t→∞, which corresponds to a localization in the case of an initial qubit state. The second one is Xt⁄t as t→∞, whose limit density is given by the Konno density function [1–4]. The density appears in various situations of discrete-time cases. The corresponding similar limit theorem was proved in [5] for a continuous-time case on the homogeneous tree.
Based on studies of four specific networks, we conjecture a general relation between the walk dimensions dw{d}_{w}dw​ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that dw{d}_{w}dw​ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\ensuremath{\rho}(x,t)$ in space and time of this quantum-walk equation exhibits a scaling collapse for a variable xdw/t{x}^{{d}_{w}}/txdw​/t in the weak limit, which defines dw{d}_{w}dw​ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\ensuremath{\rho}(x,t)$ in each case with extensive numerical simulation. The exact values for dw{d}_{w}dw​ themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.
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.