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

On the Optimal Rate of Convergence for Translation-Invariant 1D Quantum Walks

Benjamin Hinrichs, Pascal Mittenbühler

math-phquant-phSubmitted Nov 17, 2025• Announced Nov 18, 2025• 0 citations• Revised Jan 26, 2026 (v2)
v1 · Nov 17, 2025v2 · Jan 26, 2026
arXivHTMLPDF

Abstract

We study the convergence rate of translation-invariant discrete-time quantum dynamics on a one-dimensional lattice. We prove that the cumulative distributions function of the ballistically scaled position $X(n)/{n}$ after $n$ steps converges at a rate of $n^{-1/3}$ in the Lévy metric as $n\to\infty$. In the special case of step-coin quantum walks with two-dimensional coin space, we recover the same convergence rate for the supremum distance and prove optimality.

Comments
20 pages

Related papers

Asymptotic evolution of quantum walks with random coin

André Ahlbrecht, Holger Vogts, Albert H. Werner +1 more

We study the asymptotic position distribution of general quantum walks on a lattice, including walks with a random coin, which is chosen from step to step by a general Markov chain. In the unitary (i.e., nonrandom) case, we allow any unitary operator which commutes with translations and couples only sites at a finite distance from each other. For example, a single step of the walk could be composed of any finite succession of different shift and coin operations in the usual sense, with any lattice dimension and coin dimension. We find ballistic scaling and establish a direct method for computing the asymptotic distribution of position divided by time, namely as the distribution of the discrete time analog of the group velocity. In the random case, we let a Markov chain (control process) pick in each step one of finitely many unitary walks, in the sense described above. In ballistic order, we find a nonrandom drift which depends only on the mean of the control process and not on the initial state. In diffusive scaling, the limiting distribution is asymptotically Gaussian, with a covariance matrix (diffusion matrix) depending on momentum. The diffusion matrix depends not only on the mean but also on the transition rates of the control process. In the nonrandom limit, i.e., when the coins chosen are all very close or the transition rates of the control process are small, leading to long intervals of ballistic evolution, the diffusion matrix diverges. Our method is based on spatial Fourier transforms, and the first and second order perturbation theory of the eigenvalue 1 of the transition operator for each value of the momentum.

arXiv:1009.2019•Journal of Mathematical Physics•Apr 1, 2011•119 citations

Convergence of coined quantum walks on d-dimensional Euclidean space

Alex D. Gottlieb, Svante Janson, Petra F. Scudo

Coined quantum walks may be interpreted as the motion in position space of a quantum particle with a spin degree of freedom; the dynamics are determined by iterating a unitary transformation which is the product of a spin transformation and a translation conditional on the spin state. Coined quantum walks on the d-dimensional lattice can be treated as special cases of coined quantum walks on d-dimensional Euclidean space. We study quantum walks on d-dimensional Euclidean space and prove that the sequence of rescaled probability distributions in position space associated to the unitary evolution of the particle converges to a limit distribution.

arXiv:quant-ph/0406072•Jun 11, 2004•0 citations

Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice

Da’er Feng, Shengshi Pang

The quantum walk is a quantum counterpart of the classical random walk that exhibits nonclassical behaviors and outperforms the classical random walk in various aspects. It has been known that a single particle can be propagated by a discrete-time quantum walk with a quadratic time scaling in the variance of position distribution, beating the linear time scaling in a classical random walk. In this paper, we consider the discrete-time quantum walk for multiple particles in a one-dimensional lattice, and investigate the optimization of the joint coin state to enhance the spatial propagation of the particles in the lattice. We study the asymptotic evolution of position distribution for multiple particles in the long-time limit, and analytically optimize the joint coin state to derive the maximum variance of the position distribution between the particles after the evolution of the quantum walk. An interesting result is that an optimized coin state always possesses specific exchange symmetry which can be characterized by a graph consisting of two disconnected complete subgraphs and the exchange symmetry can significantly influence the position correlations between the particles, showing the critical role of coin symmetry in the propagation of multiple particles by the quantum walk. We further study the entanglement of the optimized coin states to show the relation of the coin correlations to the particle position distribution.

arXiv:2212.05452•Physical Review A•May 1, 2024•1 citation

Limit distributions of two-dimensional quantum walks

恭平 渡部, Naoki Kobayashi, Makoto Katori +1 more

One-parameter family of discrete-time quantum-walk models on the square lattice, which includes the Grover-walk model as a special case, is analytically studied. Convergence in the long-time limit $t\ensuremath{\rightarrow}\ensuremath{\infty}$ of all joint moments of two components of walker's pseudovelocity, ${X}_{t}/t$ and ${Y}_{t}/t$, is proved and the probability density of limit distribution is derived. Dependence of the two-dimensional limit density function on the parameter of quantum coin and initial four-component qudit of quantum walker is determined. Symmetry of limit distribution on a plane and localization around the origin are completely controlled. Comparison with numerical results of direct computer simulations is also shown.

arXiv:0802.2749•Physical Review A•Jun 19, 2008•91 citations

Asymptotic behavior of decoherent and interacting quantum walks

André Ahlbrecht

In this thesis we study the propagation behavior of quantum particles which perform discrete-time quantum walks on spatial lattices.By definition, quantum walks are discrete-time evolutions such that a single time step couples only neighboring lattice sites.Additionally, we assume in this thesis that the dynamical law commutes with all translations of the spatial lattice, that is we consider translationally invariant quantum walks.The results presented in the following are separated into two parts: The first part is devoted to the study of single-particle quantum walks, and in the second part we investigate quantum walks of several particles.Single-particle quantum walks: Our aim is to study the asymptotic behavior of particles undergoing general translationally invariant quantum walks.Employing perturbation theory, we establish a direct method for computing the asymptotic distribution of the particle's position rescaled by an appropriate time-dependent factor.If the time evolution is implemented by a unitary operator commuting with all lattice translations and with empty pure point spectrum, we find linear scaling of the asymptotic position distribution.In this case, the asymptotic distribution of position divided by time is determined by the analog of the group velocity.If, on the other hand, the quantum walk is subject to decoherence, we expect that it behaves like a classical random walk.We provide explicit criteria under which this intuitive statement is true, that is, the asymptotic scaling of the particle's position distribution is that of a diffusion process.We find that the asymptotic distribution of position divided by the square root of time is a mixture of Gaussians in this case.However, we also provide examples of decoherent quantum walks which violate these criteria, and exhibit linear scaling of the asymptotic position distribution. Many-particle quantum walks:We investigate unitary quantum walks of two particles with collisional interactions.That is, the particles perform independent single-particle quantum walks if they are at distinct lattice sites, and an interaction takes place if both particles occupy the same lattice site.We prove that such quantum walks generically exhibit a molecular binding effect between the particles.More precisely, for a measurement of the particles' positions we have a bound on the probability to obtain a certain result which decays exponentially with the particles' distance.As a preparatory step for this analysis, we consider single-particle quantum walks with point defects, and provide a method to compute their eigenvalues in the spectral gap of the quantum walk without defect.We further generalize our model to arbitrary numbers of particles and study the behavior of local excitations in many-particle quantum walks.

•Jan 1, 2013•1 citation

One-dimensional quantum walks via generating function and the CGMV method

Norio Konno, Etsuo Segawa

We treat quantum walk (QW) on the line whose quantum coin at each vertex tends to the identity as the distance goes to infinity. We obtain a limit theorem that this QW exhibits localization with not an exponential but a ``power-law" decay around the origin and a ``strongly" ballistic spreading called bottom localization in this paper. This limit theorem implies the weak convergence with linear scaling whose density has two delta measures at $x=0$ (the origin) and $x=1$ (the bottom) without continuous parts.

arXiv:1305.1722•Quantum Information and Computation•Oct 1, 2014•7 citations
We study the convergence rate of translation-invariant discrete-time quantum dynamics on a one-dimensional lattice. We prove that the cumulative distributions function of the ballistically scaled position X(n)/nX(n)/{n}X(n)/n after nnn steps converges at a rate of n−1/3n^{-1/3}n−1/3 in the Lévy metric as n→∞n\to\inftyn→∞. In the special case of step-coin quantum walks with two-dimensional coin space, we recover the same convergence rate for the supremum distance and prove optimality.
We study the asymptotic position distribution of general quantum walks on a lattice, including walks with a random coin, which is chosen from step to step by a general Markov chain. In the unitary (i.e., nonrandom) case, we allow any unitary operator which commutes with translations and couples only sites at a finite distance from each other. For example, a single step of the walk could be composed of any finite succession of different shift and coin operations in the usual sense, with any lattice dimension and coin dimension. We find ballistic scaling and establish a direct method for computing the asymptotic distribution of position divided by time, namely as the distribution of the discrete time analog of the group velocity. In the random case, we let a Markov chain (control process) pick in each step one of finitely many unitary walks, in the sense described above. In ballistic order, we find a nonrandom drift which depends only on the mean of the control process and not on the initial state. In diffusive scaling, the limiting distribution is asymptotically Gaussian, with a covariance matrix (diffusion matrix) depending on momentum. The diffusion matrix depends not only on the mean but also on the transition rates of the control process. In the nonrandom limit, i.e., when the coins chosen are all very close or the transition rates of the control process are small, leading to long intervals of ballistic evolution, the diffusion matrix diverges. Our method is based on spatial Fourier transforms, and the first and second order perturbation theory of the eigenvalue 1 of the transition operator for each value of the momentum.
Coined quantum walks may be interpreted as the motion in position space of a quantum particle with a spin degree of freedom; the dynamics are determined by iterating a unitary transformation which is the product of a spin transformation and a translation conditional on the spin state. Coined quantum walks on the d-dimensional lattice can be treated as special cases of coined quantum walks on d-dimensional Euclidean space. We study quantum walks on d-dimensional Euclidean space and prove that the sequence of rescaled probability distributions in position space associated to the unitary evolution of the particle converges to a limit distribution.
The quantum walk is a quantum counterpart of the classical random walk that exhibits nonclassical behaviors and outperforms the classical random walk in various aspects. It has been known that a single particle can be propagated by a discrete-time quantum walk with a quadratic time scaling in the variance of position distribution, beating the linear time scaling in a classical random walk. In this paper, we consider the discrete-time quantum walk for multiple particles in a one-dimensional lattice, and investigate the optimization of the joint coin state to enhance the spatial propagation of the particles in the lattice. We study the asymptotic evolution of position distribution for multiple particles in the long-time limit, and analytically optimize the joint coin state to derive the maximum variance of the position distribution between the particles after the evolution of the quantum walk. An interesting result is that an optimized coin state always possesses specific exchange symmetry which can be characterized by a graph consisting of two disconnected complete subgraphs and the exchange symmetry can significantly influence the position correlations between the particles, showing the critical role of coin symmetry in the propagation of multiple particles by the quantum walk. We further study the entanglement of the optimized coin states to show the relation of the coin correlations to the particle position distribution.
One-parameter family of discrete-time quantum-walk models on the square lattice, which includes the Grover-walk model as a special case, is analytically studied. Convergence in the long-time limit $t\ensuremath{\rightarrow}\ensuremath{\infty}$ of all joint moments of two components of walker's pseudovelocity, Xt/t{X}_{t}/tXt​/t and Yt/t{Y}_{t}/tYt​/t, is proved and the probability density of limit distribution is derived. Dependence of the two-dimensional limit density function on the parameter of quantum coin and initial four-component qudit of quantum walker is determined. Symmetry of limit distribution on a plane and localization around the origin are completely controlled. Comparison with numerical results of direct computer simulations is also shown.
In this thesis we study the propagation behavior of quantum particles which perform discrete-time quantum walks on spatial lattices.By definition, quantum walks are discrete-time evolutions such that a single time step couples only neighboring lattice sites.Additionally, we assume in this thesis that the dynamical law commutes with all translations of the spatial lattice, that is we consider translationally invariant quantum walks.The results presented in the following are separated into two parts: The first part is devoted to the study of single-particle quantum walks, and in the second part we investigate quantum walks of several particles.Single-particle quantum walks: Our aim is to study the asymptotic behavior of particles undergoing general translationally invariant quantum walks.Employing perturbation theory, we establish a direct method for computing the asymptotic distribution of the particle's position rescaled by an appropriate time-dependent factor.If the time evolution is implemented by a unitary operator commuting with all lattice translations and with empty pure point spectrum, we find linear scaling of the asymptotic position distribution.In this case, the asymptotic distribution of position divided by time is determined by the analog of the group velocity.If, on the other hand, the quantum walk is subject to decoherence, we expect that it behaves like a classical random walk.We provide explicit criteria under which this intuitive statement is true, that is, the asymptotic scaling of the particle's position distribution is that of a diffusion process.We find that the asymptotic distribution of position divided by the square root of time is a mixture of Gaussians in this case.However, we also provide examples of decoherent quantum walks which violate these criteria, and exhibit linear scaling of the asymptotic position distribution. Many-particle quantum walks:We investigate unitary quantum walks of two particles with collisional interactions.That is, the particles perform independent single-particle quantum walks if they are at distinct lattice sites, and an interaction takes place if both particles occupy the same lattice site.We prove that such quantum walks generically exhibit a molecular binding effect between the particles.More precisely, for a measurement of the particles' positions we have a bound on the probability to obtain a certain result which decays exponentially with the particles' distance.As a preparatory step for this analysis, we consider single-particle quantum walks with point defects, and provide a method to compute their eigenvalues in the spectral gap of the quantum walk without defect.We further generalize our model to arbitrary numbers of particles and study the behavior of local excitations in many-particle quantum walks.
We treat quantum walk (QW) on the line whose quantum coin at each vertex tends to the identity as the distance goes to infinity. We obtain a limit theorem that this QW exhibits localization with not an exponential but a ``power-law" decay around the origin and a ``strongly" ballistic spreading called bottom localization in this paper. This limit theorem implies the weak convergence with linear scaling whose density has two delta measures at x=0x=0x=0 (the origin) and x=1x=1x=1 (the bottom) without continuous parts.