1. Limit theorems and absorption problems for quantum random walks in one dimension
Norio Konno
Quantum Information and Computation, Vol.2, Special, pp.578-595 (2002)
http://arxiv.org/abs/quant-ph/0210011
In this paper we consider limit theorems, symmetry of distribution, and absorption problems for two types of one-dimensional quantum random walks determined by 2 times 2 unitary matrices using our PQRS method. The one type was introduced by Gudder in 1988, and the other type was studied intensively by Ambainis et al. in 2001. The difference between both types of quantum random walks is also clarified.
2. Quantum Certificate Complexity
Scott Aaronson
http://arxiv.org/abs/quant-ph/0210020
Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation R0(f) = O(Q2(f)^2 Q0(f) log n) for total f, where R0, Q2, and Q0 are zero-error randomized, bounded-error quantum, and zero-error quantum query complexities respectively. Finally we give asymptotic gaps between the measures, including a total f for which C(f) is superquadratic in QC(f), and a symmetric partial f for which QC(f) = O(1) yet Q2(f) = Omega(n/log n).
3. Decoherence in a quantum walk on the line
Viv Kendon, Ben Tregenna
http://arxiv.org/abs/quant-ph/0210047
We have studied how decoherence affects a quantum walk on the line. As expected, it is highly sensitive, consisting as it does of an extremely delocalized particle. We obtain an expression for the rate at which the standard deviation falls from the quantum value as decoherence increases and show that it is proportional to the number of decoherence "events" occuring during the walk.
4. The underlying digraph of a coined quantum random walk
Simone Severini
http://arxiv.org/abs/quant-ph/0210055
We give a characterization of the line digraph of a regular digraph. We make use of the characterization, to show that the underlying digraph of a coined quantum random walk is a line digraph. We remark the connection between line digraphs and in-split graphs in symbolic dynamics.
5. A Quantum Random Walk Search Algorithm
Neil Shenvi, Julia Kempe, K. Birgitta Whaley
Phys. Rev. A, Vol. 67 (5), 052307 (2003)
http://arxiv.org/abs/quant-ph/0210064
Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speed-up over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random walk architecture that provides such a speed-up. It will be shown that this algorithm performs an oracle search on a database of $N$ items with $O(\sqrt{N})$ calls to the oracle, yielding a speed-up similar to other quantum search algorithms. It appears that the quantum random walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms.
6. Quantum Walks driven by many coins
Todd A. Brun, Hilary A. Carteret, Andris Ambainis
Phys. Rev. A 67, 052317 (2003).
http://arxiv.org/abs/quant-ph/0210161
Quantum random walks have been much studied recently, largely due to their highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum random walk on the line: the use of multiple quantum ``coins'' in order to diminish the effects of interference between paths. We find solutions to this system in terms of the single coin random walk, and compare the asymptotic limit of these solutions to numerical simulations. We find exact analytical expressions for the time-dependence of the first two moments, and show that in the long time limit the ``quantum mechanical'' behavior of the one-coin walk persists. We further show that this is generic for a very broad class of possible walks, and that this behavior disappears only in the limit of a new coin for every step of the walk.
7. Quantum random walks with decoherent coins
Todd A. Brun, Hilary A. Carteret, Andris Ambainis
Phys. Rev. A 67, 032304 (2003).
http://arxiv.org/abs/quant-ph/0210180
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.