1. Hitting Time of Quantum Walks with Perturbation
Chen-Fu Chiang, Guillermo Gomez
Quantum Information Processing (Feb. 9), pp.~1-12, Springer, (2012)
http://arxiv.org/abs/1107.2965
The hitting time is the required minimum time for a Markov chain-based walk (classical or quantum) to reach a target state in the state space. We investigate the effect of the perturbation on the hitting time of a quantum walk. We obtain an upper bound for the perturbed quantum walk hitting time by applying Szegedy's work and the perturbation bounds with Weyl's perturbation theorem on classical matrix. Based on the definition of quantum hitting time given in MNRS algorithm, we further compute the delayed perturbed hitting time (DPHT) and delayed perturbed quantum hitting time (DPQHT). We show that the upper bound for DPQHT is actually greater than the difference between the square root of the upper bound for a perturbed random walk and the square root of the lower bound for a random walk.
2. Asymptotic distributions of quantum walks on the line with two entangled coins
Chaobin Liu
http://arxiv.org/abs/1107.3346
We advance the previous studies of quantum walks on the line with two coins. Such four-state quantum walks driven by a three-direction shift operator may have nonzero stationary distributions (localization), thus distinguishing themselves from the quantum walks on the line in the basic scenario (i.e., driven by a single coin). In this work, asymptotic position distributions of the quantum walks are examined. We derive a weak limit for the quantum walks and explicit formulas of stationary probability distribution, whose dependencies on the coin parameter and the initial state of quantum walks are presented. In particular, it is shown that the weak limit for the present quantum walks can be of the form in the basic scenario of quantum walks on the line, for certain initial states of the walk and certain values of the coin parameter. In the case where localization occurs, we show that the stationary probability exponentially decays with the absolute value of a walker's position, independent of the parity of time.
3. Where to quantum walk
Viv Kendon
http://arxiv.org/abs/1107.3795
Quantum versions of random walks have diverse applications that are motivating experimental implementations as well as theoretical studies. However, the main impetus behind this interest is their use in quantum algorithms, which have always employed the quantum walk in the form of a program running on a quantum computer. Recent results showing that quantum walks are "universal for quantum computation" relate entirely to algorithms, and do not imply that a physical quantum walk could provide a new architecture for quantum computers. Nonetheless, quantum walks used to model transport phenomena in spin chains and biomolecules broaden their scope well beyond algorithms, and reopen the question of when a physical implementation might provide useful computational outputs. In this article we determine the conditions under which a physical quantum walk experiment could provide useful results beyond the reach of classical computation.
4. Framework for discrete-time quantum walks and a symmetric walk on a binary tree
Zlatko Dimcovic, Daniel Rockwell, Ian Milligan, Robert M. Burton, Thinh Nguyen, Yevgeniy Kovchegov
Phys. Rev. A 84, 032311 (2011)
http://arxiv.org/abs/1107.4201
We formulate a framework for discrete-time quantum walks, motivated by classical random walks with memory. We present a specific representation of the classical walk with memory 2 on which this is based. The framework has no need for coin spaces, it imposes no constraints on the evolution operator other than unitarity, and is unifying of other approaches. As an example we construct a symmetric discrete-time quantum walk on the semi-infinite binary tree. The generating function of the amplitude at the root is computed in closed-form, as a function of time and the initial level n in the tree, and we find the asymptotic and a full numerical solution for the amplitude. It exhibits a sharp interference peak and a power law tail, as opposed to the exponentially decaying tail of a broadly peaked distribution of the classical symmetric random walk on a binary tree. The probability peak is orders of magnitude larger than it is for the classical walk (already at small n). The quantum walk shows a polynomial algorithmic speedup in n over the classical walk, which we conjecture to be of the order 2/3, based on strong trends in data.
5. Alternate two-dimensional quantum walk with a single-qubit coin
C. Di Franco, M. Mc Gettrick, T. Machida, Th. Busch
Phys. Rev. A 84, 042337 (2011)
http://arxiv.org/abs/1107.4400
We have recently proposed a two-dimensional quantum walk where the requirement of a higher dimensionality of the coin space is substituted with the alternance of the directions in which the walker can move [C. Di Franco, M. Mc Gettrick, and Th. Busch, Phys. Rev. Lett. {\bf 106}, 080502 (2011)]. For a particular initial state of the coin, this walk is able to perfectly reproduce the spatial probability distribution of the non-localized case of the Grover walk. Here, we present a more detailed proof of this equivalence. We also extend the analysis to other initial states, in order to provide a more complete picture of our walk. We show that this scheme outperforms the Grover walk in the generation of $x$-$y$ spatial entanglement for any initial condition, with the maximum entanglement obtained in the case of the particular aforementioned state. Finally, the equivalence is generalized to wider classes of quantum walks and a limit theorem for the alternate walk in this context is presented.
6. Limit measures of inhomogeneous discrete-time quantum walks in one dimension
Norio Konno, Tomasz Luczak, Etsuo Segawa
Quantum Information Processing 12 (2013) pp. 33-53
http://arxiv.org/abs/1107.4462
We treat three types of measures of the quantum walk (QW) with the spatial perturbation at the origin, which was introduced by [1]: time averaged limit measure, weak limit measure, and stationary measure. From the first two measures, we see a coexistence of the ballistic and localized behaviors in the walk as a sequential result following [1,2]. We propose a universality class of QWs with respect to weak limit measure. It is shown that typical spatial homogeneous QWs with ballistic spreading belong to the universality class. We find that the walk treated here with one defect also belongs to the class. We mainly consider the walk starting from the origin. However when we remove this restriction, we obtain a stationary measure of the walk. As a consequence, by choosing parameters in the stationary measure, we get the uniform measure as a stationary measure of the Hadamard walk and a time averaged limit measure of the walk with one defect respectively.
7. Electron random walk in ideal phonon gas. Exact dressed electron density matrix evolution equations
Yu.E.Kuzovlev
http://arxiv.org/abs/1107.3240
An original approach is suggested to analysis of full quantum Liouville equation for single electron (quantum particle) interacting with ideal phonon gas (harmonic boson thermostat). It is shown that under the thermodynamic limit this equation can be exactly reduced to a system of evolution equations connecting density matrix of the electron and its simplest irreducible correlations with amplitudes of one, two, three and more phonon modes. Possible application of these new equations to explanation of the electron mobility 1/f-type fluctuations in semiconductors and other media is discussed. The special case of electron in static disorder is also considered.