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.     

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.     

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.     

Two models of quantum random walk

We present an overview of two models of quantum random walk. In the first model, the discrete quantum random walk, we present the explicit solution for the recurring amplitude of the quantum random walk on a one-dimensional lattice. We also introduce a new method of solving the problem of random walk in the most general case and use it to derive the hitting amplitude for quantum random walk on the hypercube. The second is a special model based on a local interaction between neighboring spin-1/2 particles on a one-dimensional lattice. We present explicit results for the relevant quantities and obtain an upper bound on the speed of convergence to limiting probability distribution.     

Scattering quantum random walk

Random processes are of interest not only from the theoretical point of view but also for practical use in algorithms for investigating large combinatorial structures. The theory of quantum computing requires implementation of classical algorithms using quantum-mechanical devices, and random walk is an obvious candidate. We present a model for quantum random walk that is based on an interferometric analogy, can be easily implemented, and is a generalization of a former model of quantum random walk proposed by Aharonov and colleagues.     

A quantum walk in phase space with resonator-assisted double quantum dots

We implement a quantum walk in phase space with a new mechanism based on the superconducting resonator-assisted double quantum dots.By analyzing the hybrid system,we obtain the necessary factors implementing a quantum walk in phase space:the walker,coin,coin flipping and conditional phase shift.The coin flipping is implemented by adding a driving field to the resonator.The interaction between the quantum dots and resonator is used to implement conditional phase shift.Furthermore,we show that with different driving fields the quantum walk in phase space exhibits a ballistic behavior over 25 steps and numerically analyze the factors influencing the spreading of the walker in phase space.     

Electronic excitations and transport in aperiodic sequences of quantum dots in external electric and magnetic fields

The energy spectra and transport of electronic excitations in one-dimensional aperiodic sequences of quantum dots of Thue-Morse and double-periodic type are studied. The influence of external magnetic and electric fields on the energy spectra and transport is considered. For aperiodic sequences of quantum dots, in contrast to aperiodic sequences of atoms, the influence of relatively small magnetic and electric fields is essential, but localization occurs at finite values of the perturbations. The transmission coefficient is determined using the quasiclassical approximation with the Coulomb blockade taken into account. The resonance tunneling is studied.     

The red queen's walk

We study a new type of walk with memory which might serve as a toy model for the behavior one must adopt to avoid exhaustion of resources and attraction of parasites and predators. The walk takes place on a regular square lattice with periodic boundary conditions. Although the walk is completely deterministic, it mimics a “true” self-avoiding walk, i.e. a random walk with weak autocorrelation. This shows that the Red Queen effect can lead to aperiodic behavior. In addition to the case of single walkers in a flat landscape we also study the cases of hilly landscapes and of several walkers performing simultaneous walks.     

Free-Fall Non-Universality in Quantum Theory

The author shows by embodying the Einstein equivalence principle—local Poincaré invariance—and general covariance in quantum theory that wave-function spreading rules out the universality of free fall, that is, the free-fall trajectory of a quantum (test) particle depends on its internal properties. The author provides a quantitative estimate of the free-fall non-universality in terms of the Eötvös parameter, which turns out to be measurable in atom interferometry.     

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.     

Statistical description of eigenfunctions in chaotic and weakly disordered systems beyond universality

We present a semiclassical approach to eigenfunction statistics in chaotic and weakly disordered quantum systems which goes beyond random matrix theory, supersymmetry techniques, and existing semiclassical methods. The approach is based on a generalization of Berry's random wave model, combined with a consistent semiclassical representation of spatial two-point correlations. We derive closed expressions for arbitrary wave-function averages in terms of universal coefficients and sums over classical paths, which contain, besides the supersymmetry results, novel oscillatory contributions. Their physical relevance is demonstrated in the context of Coulomb blockade physics.     

Comparative study of the critical behavior in one-dimensional random and aperiodic environments

We consider cooperative processes (quantum spin chains and random walks) in one-dimensional fluctuating random and aperiodic environments characterized by fluctuating exponents . At the critical point the random and aperiodic systems scale essentially anisotropically in a similar fashion: length (L) and time (t) scales are related as . Also some critical exponents, characterizing the singularities of average quantities, are found to be universal functions of , whereas some others do depend on details of the distribution of the disorder. In the off-critical region there is an important difference between the two types of environments: in aperiodic systems there are no extra (Griffiths)-singularities. Received: 5 February 1998 / Accepted: 17 April 1998     

Open Quantum Random Walks with Decoherence on Coins with n Degrees of Freedom

In this paper we define a new type of decoherent quantum random walk with parameter 0≤p≤1, which becomes a unitary quantum random walk (UQRW) when p=0 and an open quantum random walk (OQRW) when p=1, respectively. We call this process a partially open quantum random walk (POQRW). We study the limiting distribution of a POQRW on Z ¹ subject to decoherence on coins with n degrees of freedom. The limiting distribution of the POQRW converges to a convex combination of normal distributions, under an eigenvalue condition. A Perron-Frobenius type of theorem is established to determine whether or not a POQRW satisfies the eigenvalue condition. Moreover, we explicitly compute the limiting distributions of characteristic equations of the position probability functions when n=2 and 3.     

Open Quantum Random Walks

A new model of quantum random walks is introduced, on lattices as well as on finite graphs. These quantum random walks take into account the behavior of open quantum systems. They are the exact quantum analogues of classical Markov chains. We explore the “quantum trajectory” point of view on these quantum random walks, that is, we show that measuring the position of the particle after each time-step gives rise to a classical Markov chain, on the lattice times the state space of the particle. This quantum trajectory is a simulation of the master equation of the quantum random walk. The physical pertinence of such quantum random walks and the way they can be concretely realized is discussed. Differences and connections with the already well-known quantum random walks, such as the Hadamard random walk, are established.     

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.     

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.     

Quantum to classical transition for random walks

We look at two possible routes to classical behavior for the discrete quantum random walk on the integers: decoherence in the quantum "coin" which drives the walk, or the use of higher-dimensional (or multiple) coins to dilute the effects of interference. We use the position variance as an indicator of classical behavior and find analytical expressions for this in the long-time limit; we see that the multicoin walk retains the "quantum" quadratic growth of the variance except in the limit of a new coin for every step, while the walk with decoherence exhibits "classical" linear growth of the variance even for weak decoherence.     

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