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

Journal of Physics A Mathematical and Theoretical

The ‘t/2 law’ for quantum random walks on the line starting in the classical state

Chaobin Liu

Published Jul 29, 2008• 3 citations
Publisher

Abstract

Based on the theory of unitary matrices, our treatment of the theory of quantum random walks simplifies and clarifies certain prior derivations based on Fourier transform methods. Given a quantum random walk on the line determined by a 2× 2 unitary matrix U , we show how the first two moments of the position probability distribution are determined by the eigenvalues of U . By varying the ‘coin operator’ A , we show that the leading term of the standard deviation of the position probability distribution is ct , where t denotes time and 0 ⩽ c ⩽ 1. However, it turns out that the maximum value of c , namely c = 1, is achievable when and only when the coin operator A is diagonal, and the initial state is unbiased. Starting in the classical state |0⟩ ⊗ |1⟩, our approach confirms that the maximum value of the leading term of the standard deviation of the position probability distribution is , which, by way of known examples, is verified to be achievable.

DOI
10.1088/1751-8113/41/35/355306

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

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.

•Aug 16, 2016•19 citations

Quantum random walks with decoherent coins

Todd A. Brun, Hilary A. Carteret, Andris Ambainis

The quantum random walk has been much studied recently, largely due to its highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum walk on the line: the presence of decoherence in the quantum ``coin'' which drives the walk. We find exact analytical expressions for the time dependence of the first two moments of position, and show that in the long-time limit the variance grows linearly with time, unlike the unitary walk. We compare this to the results of direct numerical simulation, and see how the form of the position distribution changes from the unitary to the usual classical result as we increase the strength of the decoherence.

arXiv:quant-ph/0210180•Physical Review A•Mar 14, 2003•155 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

A QUANTUM WALK WITH A DELOCALIZED INITIAL STATE: CONTRIBUTION FROM A COIN-FLIP OPERATOR

Takuya Machida

A unit evolution step of discrete-time quantum walks (QWs) is determined by both a coin-flip operator and a position-shift operator. The behavior of quantum walkers after many steps delicately depends on the coin-flip operator and an initial condition of the walk. To get the behavior, a lot of long-time limit distributions for the QWs starting with a localized initial state have been derived. In this paper, we compute limit distributions of a 2-state QW with a delocalized initial state, not a localized initial state, and discuss how the walker depends on the coin-flip operator. The initial state induced from the Fourier series expansion, which is called the (α, β) delocalized initial state in this paper, provides different limit density functions from the ones of the quantum walk with a localized initial state.

arXiv:1203.5396•International Journal of Quantum Information•Aug 1, 2013•7 citations

One-dimensional quantum random walks with two entangled coins

Chaobin Liu, Nelson Petulante

We offer theoretical explanations for some recent observations in numerical simulations of quantum random walks (QRWs). Specifically, in the case of a QRW on the line with one particle (walker) and two entangled coins, we explain the phenomenon, called ``localization,'' whereby the probability distribution of the walker's position is seen to exhibit a persistent major ``spike'' (or ``peak'') at the initial position and two other minor spikes which drift to infinity in either direction. Another interesting finding in connection with QRWs of this sort pertains to the limiting behavior of the position probability distribution. It is seen that the probability of finding the walker at any given location eventually becomes stationary and nonvanishing. We explain these observations in terms of the degeneration of some eigenvalue of the time evolution operator $U(k)$. An explicit general formula is derived for the limiting probability, from which we deduce the limiting value of the height of the observed spike at the origin. We show that the limiting probability decreases quadratically for large values of the position $x$. We locate the two minor spikes and demonstrate that their positions are determined by the phases of nondegenerated eigenvalues of $U(k)$. Finally, for fixed time $t$ sufficiently large, we examine the dependence on $t$ of the probability of finding a particle at a given location $x$.

arXiv:0807.2263•Physical Review A•Mar 12, 2009•44 citations
Based on the theory of unitary matrices, our treatment of the theory of quantum random walks simplifies and clarifies certain prior derivations based on Fourier transform methods. Given a quantum random walk on the line determined by a 2× 2 unitary matrix U , we show how the first two moments of the position probability distribution are determined by the eigenvalues of U . By varying the ‘coin operator’ A , we show that the leading term of the standard deviation of the position probability distribution is ct , where t denotes time and 0 ⩽ c ⩽ 1. However, it turns out that the maximum value of c , namely c = 1, is achievable when and only when the coin operator A is diagonal, and the initial state is unbiased. Starting in the classical state |0⟩ ⊗ |1⟩, our approach confirms that the maximum value of the leading term of the standard deviation of the position probability distribution is , which, by way of known examples, is verified to be achievable.
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.
We consider the discrete time unitary dynamics given by a quantum walk on the lattice Zd\Z^dZd 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 Zd\Z^dZd 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.
The quantum random walk has been much studied recently, largely due to its highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum walk on the line: the presence of decoherence in the quantum ``coin'' which drives the walk. We find exact analytical expressions for the time dependence of the first two moments of position, and show that in the long-time limit the variance grows linearly with time, unlike the unitary walk. We compare this to the results of direct numerical simulation, and see how the form of the position distribution changes from the unitary to the usual classical result as we increase the strength of the decoherence.
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.
A unit evolution step of discrete-time quantum walks (QWs) is determined by both a coin-flip operator and a position-shift operator. The behavior of quantum walkers after many steps delicately depends on the coin-flip operator and an initial condition of the walk. To get the behavior, a lot of long-time limit distributions for the QWs starting with a localized initial state have been derived. In this paper, we compute limit distributions of a 2-state QW with a delocalized initial state, not a localized initial state, and discuss how the walker depends on the coin-flip operator. The initial state induced from the Fourier series expansion, which is called the (α, β) delocalized initial state in this paper, provides different limit density functions from the ones of the quantum walk with a localized initial state.
We offer theoretical explanations for some recent observations in numerical simulations of quantum random walks (QRWs). Specifically, in the case of a QRW on the line with one particle (walker) and two entangled coins, we explain the phenomenon, called ``localization,'' whereby the probability distribution of the walker's position is seen to exhibit a persistent major ``spike'' (or ``peak'') at the initial position and two other minor spikes which drift to infinity in either direction. Another interesting finding in connection with QRWs of this sort pertains to the limiting behavior of the position probability distribution. It is seen that the probability of finding the walker at any given location eventually becomes stationary and nonvanishing. We explain these observations in terms of the degeneration of some eigenvalue of the time evolution operator U(k)U(k)U(k). An explicit general formula is derived for the limiting probability, from which we deduce the limiting value of the height of the observed spike at the origin. We show that the limiting probability decreases quadratically for large values of the position xxx. We locate the two minor spikes and demonstrate that their positions are determined by the phases of nondegenerated eigenvalues of U(k)U(k)U(k). Finally, for fixed time ttt sufficiently large, we examine the dependence on ttt of the probability of finding a particle at a given location xxx.