1. Simulation of quantum random walks using interference of classical field
H. Jeong, M. Paternostro, M. S. Kim
Phys. Rev. A 69, 012310 (2004).
http://arxiv.org/abs/quant-ph/0305008
We suggest a theoretical scheme for the simulation of quantum random walks on a line using beam splitters, phase shifters and photodetectors. Our model enables us to simulate a quantum random walk with use of the wave nature of classical light fields. Furthermore, the proposed set-up allows the analysis of the effects of decoherence. The transition from a pure mean photon-number distribution to a classical one is studied varying the decoherence parameters.
2. Distributed construction of quantum fingerprints
Andris Ambainis, Yaoyun Shi
http://arxiv.org/abs/quant-ph/0305022
Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/0102001) in obtaining an efficient quantum communication protocol. We design a protocol for constructing the fingerprint in a distributed scenario. As an application, this protocol gives rise to a communication protocol more efficient than the best known classical protocol for a communication problem.
3. What is random about a quantum random walk?
Arul Lakshminarayan
http://arxiv.org/abs/quant-ph/0305026
We use simple deterministic dynamical systems as coins in studying quantum walks. These dynamical systems can be chosen to display, in the classical limit, a range of behaviors from the integrable to chaotic, or deterministically random. As an example of an integrable coin we study the Fourier walk that generalizes the Hadamard walk and show that the walker slows down with coin dimensionality, which controls the effective Planck constant. Introducing multi-Harper maps as deterministic models of random walks we study the effect of coin chaos on the quantum walk. We also demonstrate that breaking time-reversal symmetry in the coin dynamics effectively slows down the walk.
4. Polynomial degree vs. quantum query complexity
Andris Ambainis
Journal of Computer and System Sciences, 72(2): 220-238, 2006
http://arxiv.org/abs/quant-ph/0305028
The degree of a polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity \Omega(M^{1.321...}). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.
5. From quantum theory to classical dynamics under spontaneous wave-packet reduction
C. F. Huang
http://arxiv.org/abs/quant-ph/0305146
A quantum master equation of the Lindblad form is obtained in this paper by considering the spontaneous wave-packet reduction. Different classical equations can be derived after exactly mapping such a quantum master equation to a continuous time random walk (CTRW). Although this CTRW is a quasiclassical walk, the effects due to the quantum interference can still be important in such a walk. Macroscopically, we shall consider the uncertainty of the potential and determine the effective transition probability by a family of Schr\"{o}dinger equations (or operators).
6. Optical Cavity Implementations of the Quantum Walk
Peter L. Knight, Eugenio Roldan, J.E. Sipe
Optics Communications 227, 147-157 (2003)
http://arxiv.org/abs/quant-ph/0305165
We discuss how the coined quantum walk on the line or on the circle can be implemented using optical waves. We propose several optical cavity configurations for these implementations.
7. Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
Andris Ambainis
Theory of Computing, 1:37-46, 2005
http://arxiv.org/abs/quant-ph/0305179
We give a general method for proving quantum lower bounds for problems with small range. Namely, we show that, for any symmetric problem defined on functions $f:\{1, ..., N\}\to\{1, ..., M\}$, its polynomial degree is the same for all $M\geq N$. Therefore, if we have a quantum lower bound for some (possibly, quite large) range $M$ which is shown using polynomials method, we immediately get the same lower bound for all ranges $M\geq N$. In particular, we get $\Omega(N^{1/3})$ and $\Omega(N^{2/3})$ quantum lower bounds for collision and element distinctness with small range.
8. Continuous-time quantum walks on the symmetric group
Heath Gerhardt, John Watrous
http://arxiv.org/abs/quant-ph/0305182
In this paper we study continuous-time quantum walks on Cayley graphs of the symmetric group, and prove various facts concerning such walks that demonstrate significant differences from their classical analogues. In particular, we show that for several natural choices for generating sets, these quantum walks do not have uniform limiting distributions, and are effectively blind to large areas of the graphs due to destructive interference.