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 ℤd can be treated as special cases of coined quantum walks on ℝd. We study quantum walks on ℝd 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.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 ℤd can be treated as special cases of coined quantum walks on ℝd. We study quantum walks on ℝd 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.

Infinite Dimensional Analysis Quantum Probability and Related TopicsMar 1, 200516 citations

1 Random Time-Dependent Quantum Walks

Alain Joye

We consider the discrete time unitary dynamics given by a quantum walk on the lattice $\Z^d$ performed by a quantum particle with internal degree of freedom, called coin state, according to the following iterated rule: a unitary update of the coin state takes place, followed by a shift on the lattice, conditioned on the coin state of the particle. We study the large time behavior of the quantum mechanical probability distribution of the position observable in $\Z^d$ when the sequence of unitary updates is given by an i.i.d. sequence of random matrices. When averaged over the randomness, this distribution is shown to display a drift proportional to the time and its centered counterpart is shown to display a diffusive behavior with a diffusion matrix we compute. A moderate deviation principle is also proven to hold for the averaged distribution and the limit of the suitably rescaled corresponding characteristic function is shown to satisfy a diffusion equation. A generalization to unitary updates distributed according to a Markov process is also provided. An example of i.i.d. random updates for which the analysis of the distribution can be performed without averaging is worked out. The distribution also displays a deterministic drift proportional to time and its centered counterpart gives rise to a random diffusion matrix whose law we compute. A large deviation principle is shown to hold for this example. We finally show that, in general, the expectation of the random diffusion matrix equals the diffusion matrix of the averaged distribution.We consider the discrete time unitary dynamics given by a quantum walk on the lattice $\Z^d$ performed by a quantum particle with internal degree of freedom, called coin state, according to the following iterated rule: a unitary update of the coin state takes place, followed by a shift on the lattice, conditioned on the coin state of the particle. We study the large time behavior of the quantum mechanical probability distribution of the position observable in $\Z^d$ when the sequence of unitary updates is given by an i.i.d. sequence of random matrices. When averaged over the randomness, this distribution is shown to display a drift proportional to the time and its centered counterpart is shown to display a diffusive behavior with a diffusion matrix we compute. A moderate deviation principle is also proven to hold for the averaged distribution and the limit of the suitably rescaled corresponding characteristic function is shown to satisfy a diffusion equation. A generalization to unitary updates distributed according to a Markov process is also provided. An example of i.i.d. random updates for which the analysis of the distribution can be performed without averaging is worked out. The distribution also displays a deterministic drift proportional to time and its centered counterpart gives rise to a random diffusion matrix whose law we compute. A large deviation principle is shown to hold for this example. We finally show that, in general, the expectation of the random diffusion matrix equals the diffusion matrix of the averaged distribution.

Aug 16, 201619 citations

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

Benjamin Hinrichs, Pascal Mittenbühler

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.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.

math-phCross-listedarXiv:2511.13409Nov 18, 20250 citations

Convergence theorems on multi-dimensional homogeneous quantum walks

Hiroki Sako

Abstract We propose a general framework for quantum walks on d-dimensional spaces. We investigate asymptotic behavior of these walks. We prove that every homogeneous walks with finite degree of freedom have limit distribution. This theorem can also be applied to every crystal lattice. In this theorem, it is not necessary to assume that the support of the initial unit vector is finite. We also pay attention on 1-cocycles, which is related to Heisenberg representation of time evolution of observables. For homogeneous walks with finite degree of freedom, convergence of averages of 1-cocycles associated with the position observable is also proved.Abstract We propose a general framework for quantum walks on d-dimensional spaces. We investigate asymptotic behavior of these walks. We prove that every homogeneous walks with finite degree of freedom have limit distribution. This theorem can also be applied to every crystal lattice. In this theorem, it is not necessary to assume that the support of the initial unit vector is finite. We also pay attention on 1-cocycles, which is related to Heisenberg representation of time evolution of observables. For homogeneous walks with finite degree of freedom, convergence of averages of 1-cocycles associated with the position observable is also proved.

arXiv:1903.09342Quantum Information ProcessingMar 1, 20215 citations

Projection Theorem for Discrete-Time Quantum Walks

Václav Potoček

We make and generalize the observation that summing of probability amplitudes of a discrete-time quantum walk over partitions of the walking graph consistent with the step operator results in a unitary evolution on the reduced graph which is also a quantum walk. Since the effective walking graph of the projected walk is not necessarily simpler than the original, this may bring new insights into the dynamics of some kinds of quantum walks using known results from thoroughly studied cases like Euclidean lattices. We use abstract treatment of the walking space and walker displacements in aim for a generality of the presented statements. Using this approach we also identify some pathological cases in which the projection mapping breaks down. For walks on lattices, the operation typically results in quantum walks with hyper-dimensional coin spaces. Such walks can, conversely, be viewed as projections of walks on inaccessible, larger spaces, and their properties can be inferred from the parental walk. We show that this is is the case for a lazy quantum walk, a walk with large coherent jumps and a walk on a circle with a twisted boundary condition. We also discuss the relation of this theory to the time-multiplexing optical implementations of quantum walks. Moreover, this manifestly irreversible operation can, in some cases and with a minor adjustment, be undone, and a quantum walk can be reconstructed from a set of its projections.We make and generalize the observation that summing of probability amplitudes of a discrete-time quantum walk over partitions of the walking graph consistent with the step operator results in a unitary evolution on the reduced graph which is also a quantum walk. Since the effective walking graph of the projected walk is not necessarily simpler than the original, this may bring new insights into the dynamics of some kinds of quantum walks using known results from thoroughly studied cases like Euclidean lattices. We use abstract treatment of the walking space and walker displacements in aim for a generality of the presented statements. Using this approach we also identify some pathological cases in which the projection mapping breaks down. For walks on lattices, the operation typically results in quantum walks with hyper-dimensional coin spaces. Such walks can, conversely, be viewed as projections of walks on inaccessible, larger spaces, and their properties can be inferred from the parental walk. We show that this is is the case for a lazy quantum walk, a walk with large coherent jumps and a walk on a circle with a twisted boundary condition. We also discuss the relation of this theory to the time-multiplexing optical implementations of quantum walks. Moreover, this manifestly irreversible operation can, in some cases and with a minor adjustment, be undone, and a quantum walk can be reconstructed from a set of its projections.

arXiv:2004.01332Electronic Proceedings in Theoretical Computer ScienceApr 1, 20200 citations

One-dimensional coinless quantum walks

Renato Portugal, Stefan Boettcher, Stefan Falkner

A coinless, discrete-time quantum walk possesses a Hilbert space whose dimension is smaller compared to the widely studied coined walk. Coined walks require the direct product of the site basis with the coin space; coinless walks operate purely in the site basis, which is clearly minimal. These coinless quantum walks have received considerable attention recently because they have evolution operators that can be obtained by a graphical method based on lattice tessellations and they have been shown to be as efficient as the best known coined walks when used as a quantum search algorithm. We argue that both formulations in their most general form are equivalent. In particular, we demonstrate how to transform the one-dimensional version of the coinless quantum walk into an equivalent extended coined version for a specific family of evolution operators. We present some of its basic, asymptotic features for the one-dimensional lattice with some examples of tessellations, and analyze the mixing time and limiting probability distributions on cycles.A coinless, discrete-time quantum walk possesses a Hilbert space whose dimension is smaller compared to the widely studied coined walk. Coined walks require the direct product of the site basis with the coin space; coinless walks operate purely in the site basis, which is clearly minimal. These coinless quantum walks have received considerable attention recently because they have evolution operators that can be obtained by a graphical method based on lattice tessellations and they have been shown to be as efficient as the best known coined walks when used as a quantum search algorithm. We argue that both formulations in their most general form are equivalent. In particular, we demonstrate how to transform the one-dimensional version of the coinless quantum walk into an equivalent extended coined version for a specific family of evolution operators. We present some of its basic, asymptotic features for the one-dimensional lattice with some examples of tessellations, and analyze the mixing time and limiting probability distributions on cycles.

arXiv:1408.5166Physical Review AMay 18, 201526 citations

We consider the discrete time unitary dynamics given by a quantum walk on the lattice

\Z^d

performed by a quantum particle with internal degree of freedom, called coin state, according to the following iterated rule: a unitary update of the coin state takes place, followed by a shift on the lattice, conditioned on the coin state of the particle. We study the large time behavior of the quantum mechanical probability distribution of the position observable in

\Z^d

when the sequence of unitary updates is given by an i.i.d. sequence of random matrices. When averaged over the randomness, this distribution is shown to display a drift proportional to the time and its centered counterpart is shown to display a diffusive behavior with a diffusion matrix we compute. A moderate deviation principle is also proven to hold for the averaged distribution and the limit of the suitably rescaled corresponding characteristic function is shown to satisfy a diffusion equation. A generalization to unitary updates distributed according to a Markov process is also provided. An example of i.i.d. random updates for which the analysis of the distribution can be performed without averaging is worked out. The distribution also displays a deterministic drift proportional to time and its centered counterpart gives rise to a random diffusion matrix whose law we compute. A large deviation principle is shown to hold for this example. We finally show that, in general, the expectation of the random diffusion matrix equals the diffusion matrix of the averaged distribution.

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.