1. Decoherence can be useful in quantum walks
Viv Kendon, Ben Tregenna
Pys. Rev. A 67 042315 2003
http://arxiv.org/abs/quant-ph/0209005
We present a study of the effects of decoherence in the operation of a discrete quantum walk on a line, cycle and hypercube. We find high sensitivity to decoherence, increasing with the number of steps in the walk, as the particle is becoming more delocalised with each step. However, the effect of a small amount of decoherence is to enhance the properties of the quantum walk that are desirable for the development of quantum algorithms. Specifically, we observe a highly uniform distribution on the line, a very fast mixing time on the cycle, and more reliable hitting times across the hypercube.
2. Diffusive-ballistic crossover in 1D quantum walks
Daniel K. Wojcik, J.R. Dorfman
Phys. Rev. Lett. 90 (2003) 230602
http://arxiv.org/abs/quant-ph/0209036
We show that particle transport in a uniform, quantum multi-baker map, is generically ballistic in the long time limit, for any fixed value of Planck's constant. However, for fixed times, the semi-classical limit leads to diffusion. Random matrix theory provides explicit analytical predictions for the mean square displacement of a particle in the system. These results exhibit a crossover from diffusive to ballistic motion, with crossover time from diffusive to ballistic motion on the order of the inverse of Planck's constant. We can argue, that for a large class of 1D quantum random walks, similar to the quantum multi-baker, a sufficient condition for diffusion in the semi-classical limit is classically chaotic dynamics in each cell. Using an initial equilibrium density matrix, we find that diffusive behavior is recovered in the semi-classical limit for such systems, without further interactions with the environment.
3. Quantum Lower Bound for Recursive Fourier Sampling
Scott Aaronson
Quantum Information and Computation 3(2):165-174, 2003
http://arxiv.org/abs/quant-ph/0209060
One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far from optimal. The moral is that the need to "uncompute" garbage can impose a fundamental limit on efficient quantum computation. The proof introduces a new parameter of Boolean functions called the "nonparity coefficient," which might be of independent interest.
4. Coassociative grammar, periodic orbits and quantum random walk over Z
Leroux Philippe
http://arxiv.org/abs/quant-ph/0209100
We prove that the combinatorics generated by the quantum random walk on Z can be interpreted from the reading of periodic orbits of the classical chaotic map $x \mapsto 2x mod 1$.
5. Mixing in Continuous Quantum Walks on Graphs
Amir Ahmadi, Ryan Belk, Christino Tamon, Carolyn Wendler
Quantum Information and Computation 3 (2003), 611-618.
http://arxiv.org/abs/quant-ph/0209106
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.
6. Exponential algorithmic speedup by quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman
Proc. 35th ACM Symposium on Theory of Computing (STOC 2003), pp. 59-68
http://arxiv.org/abs/quant-ph/0209131
We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time.