Quantum walk under coherence non-generating channels

We investigate the probability distribution of the quantum walk under coherence non-generating channels. We definea model called generalized classical walk with memory. Under certain conditions, generalized classical random walk withmemory can degrade into classical random walk and classical random walk with memory. Based on its various spreadingspeed, the model may be a useful tool for building algorithms. Furthermore, the model may be useful for measuring thequantumness of quantum walk. The probability distributions of quantum walks are generalized classical random walkswith memory under a class of coherence non-generating channels. Therefore, we can simulate classical random walkand classical random walk with memory by coherence non-generating channels. Also, we find that for another class ofcoherence non-generating channels, the probability distributions are influenced by the coherence in the initial state of thecoin. Nevertheless, the influence degrades as the number of steps increases. Our results could be helpful to explore therelationship between coherence and quantum walk.     

A Perron–Frobenius Type of Theorem for Quantum Operations

We define a special class of quantum operations we call Markovian and show that it has the same spectral properties as a corresponding Markov chain. We then consider a convex combination of a quantum operation and a Markovian quantum operation and show that under a norm condition its spectrum has the same properties as in the conclusion of the Perron–Frobenius theorem if its Markovian part does. Moreover, under a compatibility condition of the two operations, we show that its limiting distribution is the same as the corresponding Markov chain. We apply our general results to partially decoherent quantum random walks with decoherence strength \(0 \le p \le 1\). We obtain a quantum ergodic theorem for partially decoherent processes. We show that for \(0 < p \le 1\), the limiting distribution of a partially decoherent quantum random walk is the same as the limiting distribution for the classical random walk.     

Two Quantum Coins Sharing a Walker

For classical random walks, changing or not changing coins makes a trivial influence on the random-walk behaviors. In this paper, we investigate the quantum walk where a walker’s movement is controlled by two initially independent coins alternately partially or fully after each step. We observe that there exist complicated inter-coin correlations in the quantum walk. Specifically, we study the correlations of two coins by tracing out the walker, and analyze classical, general, and quantum correlations between two coins in terms of classical mutual information, quantum mutual information, and measurement-induced disturbance. Our analysis shows different quantum features from that in classical random walks.

     

On the Relationship Between Continuous- and Discrete-Time Quantum Walk

Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. But whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this article, I describe a precise correspondence between continuous- and discrete- time quantum walks on arbitrary graphs. Using this correspondence, I show that continuous-time quantum walk can be obtained as an appropriate limit of discrete-time quantum walks. The correspondence also leads to a new technique for simulating Hamiltonian dynamics, giving efficient simulations even in cases where the Hamiltonian is not sparse. The complexity of the simulation is linear in the total evolution time, an improvement over simulations based on high-order approximations of the Lie product formula. As applications, I describe a continuous-time quantum walk algorithm for element distinctness and show how to optimally simulate continuous-time query algorithms of a certain form in the conventional quantum query model. Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.     

One-dimensional lazy quantum walks and occupancy rate

In this paper, we discuss the properties of lazy quantum walks. Our analysis shows that the lazy quantum walks have O(t n) order of the n-th moment of the corresponding probability distribution, which is the same as that for normal quantum walks. The lazy quantum walk with a discrete Fourier transform(DFT) coin operator has a similar probability distribution concentrated interval to that of the normal Hadamard quantum walk. Most importantly, we introduce the concepts of occupancy number and occupancy rate to measure the extent to which the walk has a(relatively) high probability at every position in its range. We conclude that the lazy quantum walks have a higher occupancy rate than other walks such as normal quantum walks, classical walks, and lazy classical walks.     

二维量子随机行走及其物理实现

近年来量子随机行走相关课题因其非经典的特性,已经成为越来越多科研人员的研究热点。这篇文章中我们回顾了一维经典随机行走和一维量子随机行走模型,并且在分析两种二维经典随机行走模型的基础上,我们构建二维量子随机行走模型。通过对随机行走者的位置分布标准差的计算,我们可以证明基于这种二维量子随机行走模型的算法优于其他上述随机行走。除此之外,我们提出一个利用线性光学方法的实验方案,实现这种二维量子随机行走模型。     

Implementation of a one-dimensional quantum walk in both position and phase spaces

Quantum walks have been investigated as they have remarkably different features in contrast to classical random walks. We present a quantum walk in a one-dimensional architecture, consisting of two coins and a walker whose evolution is in both position and phase spaces alternately controlled by the two coins respectively. By analyzing the dynamics evolution of the walker in both the position and phase spaces, we observe an influence on the quantum walk in one space from that in the other space, which behaves like decoherence. We propose an implementation of the two-coin quantum walk in both position and phase spaces via cavity quantum electrodynamics(QED).     

Non-Markovian decoherent quantum walks

Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of quantum walks under different decoherence situations. In this article, we study a non-Markovian decoherent quantum walk on a line. In a short time regime, the behavior of the walk deviates from both ideal quantum walks and classical random walks. The position variance as a measure of the quantum walk collapses and revives for a short time, and tends to have a linear relation with time. That is, the walker's behavior shows a diffusive spread over a long time limit, which is caused by non-Markovian dephasing affecting the quantum correlations between the quantum walker and his coin. We also study both quantum discord and measurement-induced disturbance as measures of the quantum correlations, and observe both collapse and revival in the short time regime, and the tendency to be zero in the long time limit. Therefore, quantum walks with non-Markovian decoherence tend to have diffusive spreading behavior over long time limits, while in the short time regime they oscillate between ballistic and diffusive spreading behavior, and the quantum correlation collapses and revives due to the memory effect.     

Quantum walks: Decoherence and coin-flipping games

We investigate the global chirality distribution of the quantum walk on the line when decoherence is introduced either through simultaneous measurements of the chirality and particle position, or as a result of broken links. The first mechanism drives the system towards a classical diffusive behavior. This is used to build new quantum games, similar to the spin-flip game. The second mechanism involves two different possibilities: (a) All the quantum walk links have the same probability of being broken. (b) Only the quantum walk links on a half-line are affected by random breakage. In case (a) the decoherence drives the system to a classical Markov process, whose master equation is equivalent to the dynamical equation of the quantum density matrix. This is not the case in (b) where the asymptotic global chirality distribution unexpectedly maintains some dependence with the initial condition. Explicit analytical equations are obtained for all cases.     

Return Probability of Quantum and Correlated Random Walks

The analysis of the return probability is one of the most essential and fundamental topics in the study of classical random walks. In this paper, we study the return probability of quantum and correlated random walks in the one-dimensional integer lattice by the path counting method. We show that the return probability of both quantum and correlated random walks can be expressed in terms of the Legendre polynomial. Moreover, the generating function of the return probability can be written in terms of elliptic integrals of the first and second kinds for the quantum walk.     

Classical random walk with memory versus quantum walk on a one-dimensional infinite chain

Quantum walk is a very useful tool for building quantum algorithms due to the faster spreading of probability distributions as compared to a classical random walk. Comparing the spreading of the probability distributions of a quantum walk with that of a mnemonic classical random walk on a one-dimensional infinite chain, we find that the classical random walk could have a faster spreading than that of the quantum walk conditioned on a finite number of walking steps. Quantum walk surpasses classical random walk with memory in spreading speed when the number of steps is large enough. However, in such a situation, quantum walk would seriously suffer from decoherence. Therefore, classical walk with memory may have some advantages in practical applications.     

Random Walk of Second Class Particles in Product Shock Measures

We consider shock measures in a class of conserving stochastic particle systems on ℤ. These shock measures have a product structure with a step-like density profile and include a second class particle at the shock position. We show for the asymmetric simple exclusion process, for the exponential bricklayers’ process, and for a generalized zero range process, that under certain conditions these shocks, and therefore the second class particles, perform a simple random walk. Some previous results, including random walks of product shock measures and stationary shock measures seen from a second class particle, are direct consequences of our more general theorem. Multiple shocks can also be handled easily in this framework. Similar shock structure is also found in a nonconserving model, the branching coalescing random walk, where the role of the second class particle is played by the rightmost (or leftmost) particle.     

Group theory,Markov chains,and excluded volume effect in polymers

A restricted walk of orderr on a lattice is defined as a random walk in which polygons withr vertices or less are excluded. A study of restricted walks for increasingr provides an understanding of how the transition in properties is effected from random to self-avoiding walks which is important in our understanding of the excluded volume effect in polymers and in the study of many other problems. Here the properties of restricted walks are studied by the transition matrix method based on the theory of Markov chains. A group theoretical method is used to reduce the transition matrix governing the walk in a systematic manner and to classify the eigenvalues of the transition matrix according to the various representations of the appropriate group. It is shown that only those eigenvalues corresponding to two particular representations of the group contribute to the correlations among the steps of the walk. The distributions of eigenvalues for walks of various ordersr on the two-dimensional triangular lattice and the three-dimensional face-centered cubic lattice are presented, and they are shown to have some remarkable features.     

Irreversibility of a quantum walk induced by controllable decoherence employing random unitary operations

Quantum walk is different from random walk in reversibility and interference. Observation of the reduced re- versibility in a realistic quantum walk is of scientific interest in understanding the unique quantum behavior. We propose an idea to experimentally investigate the decoherence-induced irreversibility of quantum walks with trapped ions in phase space via the average fidelity decay. By introducing two controllable decoherence sources, i.e., the phase damping channel (i.e., dephasing) and the high temperature amplitude reservoir (i.e., dissipation), in the intervals between the steps of quantum walk, we find that the high temperature amplitude reservoir shows more detrimental effects than the phase damping channel on quantum walks. Our study also shows that the average fidelity decay works better than the position variance for characterizing the transition from quantum walks to random walk. Experimental feasibility to monitor the irreversibility is justified using currently available techniques.     

Recurrence and Pólya number of quantum walks

We analyze the recurrence probability (Pólya number) for d-dimensional unbiased quantum walks. A sufficient condition for a quantum walk to be recurrent is derived. As a by-product we find a simple criterion for localization of quantum walks. In contrast with classical walks, where the Pólya number is characteristic for the given dimension, the recurrence probability of a quantum walk depends in general on the topology of the walk, choice of the coin and the initial state. This allows us to change the character of the quantum walk from recurrent to transient by altering the initial state.     

Classical spin in a potential field

We consider an ensemble of restricted discrete random walks in 2+1 dimensions. The restriction on the walks is such as to given particles an intrinsic angular momentum. The walks are embedded in a field which affects the mean free path of the walks. We show that the dynamics of the walks is such that second-order effects are described by a discrete form of Schrödinger's equation for particles in a potential field. This provides a classical context of the equation which is independent of its quantum context.     

Asymptotic survival probability of random walks on a semi-infinite line

Symmetric and asymmetric random walks on a segment (−∞,T>0) of the real line are considered. There is a non-zero probability for the random walk to get absorbed at a site it visits. We derive for such random walks, expressions for survival probabilities in the asymptotic limit ofT→∞. An application of this asymptotic formulation to the problem of radiation transport through thick shields is presented.     

The two-state random walk

We develop asymptotic results for the two-state random walk, which can be regarded as a generalization of the continuous-time random walk. The two-state random walk is one in which a particle can be in one of two states for random periods of time, each of the states having different spatial transition probabilities. When the sojourn times in each of the states and the second moments of transition probabilities are finite, the state probabilities have an asymptotic Gaussian form. Several known asymptotic results are reproduced, such as the Gaussian form for the probability density of position in continuous-time random walks, the time spent in one of these states, and the diffusion constant of a two-state diffusing particle.     

Limit Theorems for Open Quantum Random Walks

We consider the limit distributions of open quantum random walks on one-dimensional lattice space. We introduce a dual process to the original quantum walk process, which is quite similar to the relation of Schrödinger-Heisenberg representation in quantum mechanics. By this, we can compute the distribution of the open quantum random walks concretely for many examples and thereby we can also obtain the limit distributions of them. In particular, it is possible to get rid of the initial state when we consider the evolution of the walk, it appears only in the last step of the computation.     

Computer Simulations for Some One-Dimensional Models of Random Walks in Fluctuating Random Environment

We report some results of computer simulations for two models of random walks in random environment (rwre) on the one-dimensional lattice for fixed space–time configuration of the environment (“quenched rwre”): a “Markov model” with Markov dependence in time, and a “quasi stationary” model with long range space–time correlations. We compare with the corresponding results for a model with i.i.d. (in space time) environment. In the range of times available to us the quenched distributions of the random walk displacement are far from gaussian, but as the behavior is similar for all three models one cannot exclude asymptotic gaussianity, which is proved for the model with i.i.d. environment. We also report results on the random drift and on some time correlations which show a clear power decay