1. Decoherence in quantum walks - a review
Viv Kendon
Math. Struct. in Comp. Sci 17(6) pp 1169-1220 (2006)
http://arxiv.org/abs/quant-ph/0606016
The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, led rapidly to several new quantum algorithms. These all follow unitary quantum evolution, apart from the final measurement. Since logical qubits in a quantum computer must be protected from decoherence by error correction, there is no need to consider decoherence at the level of algorithms. Nonetheless, enlarging the range of quantum dynamics to include non-unitary evolution provides a wider range of possibilities for tuning the properties of quantum walks. For example, small amounts of decoherence in a quantum walk on the line can produce more uniform spreading (a top-hat distribution), without losing the quantum speed up. This paper reviews the work on decoherence, and more generally on non-unitary evolution, in quantum walks and suggests what future questions might prove interesting to pursue in this area.
2. Connecting the discrete and continuous-time quantum walks
Frederick W. Strauch
Phys. Rev. A 74, 030301 (R) (2006)
http://arxiv.org/abs/quant-ph/0606050
Recently, quantized versions of random walks have been explored as effective elements for quantum algorithms. In the simplest case of one dimension, the theory has remained divided into the discrete-time quantum walk and the continuous-time quantum walk. Though the properties of these two walks have shown similarities, it has remained an open problem to find the exact relation between the two. The precise connection of these two processes, both quantally and classically, is presented. Extension to higher dimensions is also discussed.
3. Single atom quantum walk with 1D optical superlattices
Jaewoo Joo, P. L. Knight, Jiannis K. Pachos
http://arxiv.org/abs/quant-ph/0606087
A proposal for the implementation of quantum walks using cold atom technology is presented. It consists of one atom trapped in time varying optical superlattices. The required elements are presented in detail including the preparation procedure, the manipulation required for the quantum walk evolution and the final measurement. These procedures can be, in principle, implemented with present technology.
4. Quantum walks with infinite hitting times
Hari Krovi, Todd A. Brun
Phys. Rev. A 74, 042334 (2006)
http://arxiv.org/abs/quant-ph/0606094
Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well-defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.
5. Relativistic effects in quantum walks: Klein’s paradox and Zitterbewegung
Pawel Kurzynski
Phys. Lett. A 372, 6125 (2008)
http://arxiv.org/abs/quant-ph/0606171
Quantum walks are not only algorithmic tools for quantum computation but also not trivial models which describe various physical processes. The paper compares one-dimensional version of the free particle Dirac equation with discrete time quantum walk (DTQW). We show that the discretized Dirac equation when compared with DTQW results in interesting relations. It is also shown that two relativistic effects associated with the Dirac equation, namely Zitterbewegung (quivering motion) and Klein's paradox, are present in DTQW, which can be implemented within non-relativistic quantum mechanics.
6. Almost uniform sampling via quantum walks
Peter C. Richter
New J. Phys. 9 (2007) 72
http://arxiv.org/abs/quant-ph/0606202
Many classical randomized algorithms (e.g., approximation algorithms for #P-complete problems) utilize the following random walk algorithm for {\em almost uniform sampling} from a state space $S$ of cardinality $N$: run a symmetric ergodic Markov chain $P$ on $S$ for long enough to obtain a random state from within $\epsilon$ total variation distance of the uniform distribution over $S$. The running time of this algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} (\log N + \log \epsilon^{-1}))$, where $\delta$ is the spectral gap of $P$. We present a natural quantum version of this algorithm based on repeated measurements of the {\em quantum walk} $U_t = e^{-iPt}$. We show that it samples almost uniformly from $S$ with logarithmic dependence on $\epsilon^{-1}$ just as the classical walk $P$ does; previously, no such quantum walk algorithm was known. We then outline a framework for analyzing its running time and formulate two plausible conjectures which together would imply that it runs in time $O(\delta^{-1/2} \log N \log \epsilon^{-1})$ when $P$ is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
7. Localization and its consequences for quantum walk algorithms and quantum communication
J.P. Keating, N. Linden, J.C.F. Matthews, A. Winter
http://arxiv.org/abs/quant-ph/0606205
The exponential speed-up of quantum walks on certain graphs, relative to classical particles diffusing on the same graph, is a striking observation. It has suggested the possibility of new fast quantum algorithms. We point out here that quantum mechanics can also lead, through the phenomenon of localization, to exponential suppression of motion on these graphs (even in the absence of decoherence). In fact, for physical embodiments of graphs, this will be the generic behaviour. It also has implications for proposals for using spin networks, including spin chains, as quantum communication channels.
8. Investigation of continuous-time quantum walk by using Krylov subspace-Lanczos algorithm
M. A. Jafarizadeh, S. Salimi, R. Sufiani
http://arxiv.org/abs/quant-ph/0606241
In papers\cite{js,jsa}, the amplitudes of continuous-time quantum walk on graphs possessing quantum decomposition (QD graphs) have been calculated by a new method based on spectral distribution associated to their adjacency matrix. Here in this paper, it is shown that the continuous-time quantum walk on any arbitrary graph can be investigated by spectral distribution method, simply by using Krylov subspace-Lanczos algorithm to generate orthonormal bases of Hilbert space of quantum walk isomorphic to orthogonal polynomials. Also new type of graphs possessing generalized quantum decomposition have been introduced, where this is achieved simply by relaxing some of the constrains imposed on QD graphs and it is shown that both in QD and GQD graphs, the unit vectors of strata are identical with the orthonormal basis produced by Lanczos algorithm. Moreover, it is shown that probability amplitude of observing walk at a given vertex is proportional to its coefficient in the corresponding unit vector of its stratum, and it can be written in terms of the amplitude of its stratum. Finally the capability of Lanczos-based algorithm for evaluation of walk on arbitrary graphs (GQD or non-QD types), has been tested by calculating the probability amplitudes of quantum walk on some interesting finite (infinite) graph of GQD type and finite (infinite) path graph of non-GQD type, where the asymptotic behavior of the probability amplitudes at infinite limit of number of vertices, are in agreement with those of central limit theorem of Ref.\cite{nko}.