1. Temporal Fluctuations of Continuous-Time Quantum Random Walks on Circles
Norio Inui, Koichiro Kasahara, Yoshinao Konishi, Norio Konno
http://arxiv.org/abs/quant-ph/0402062
This work deals with both instantaneous uniform mixing property and temporal standard deviation for continuous-time quantum random walks on circles in order to study their fluctuations comparing with discrete-time quantum random walks, and continuous- and discrete-time classical random walks.
2. Storing Images in Entangled Quantum Systems
S.E. Venegas-Andraca, J.L. Ball
http://arxiv.org/abs/quant-ph/0402085
We introduce a new method of storing visual information in Quantum Mechanical systems which has certain advantages over more restricted classical memory devices. To do this we employ uniquely Quantum Mechanical properties such as Entanglement in order to store information concerning the position and shape of simple objects.
3. Limitations of Quantum Advice and One-Way Communication
Scott Aaronson
http://arxiv.org/abs/quant-ph/0402095
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly is contained in PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state" that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP is not contained in BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.
4. Coins Make Quantum Walks Faster
Andris Ambainis, Julia Kempe, Alexander Rivosh
Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005)
http://arxiv.org/abs/quant-ph/0402107
We show how to search N items arranged on a $\sqrt{N}\times\sqrt{N}$ grid in time $O(\sqrt N \log N)$, using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom, since it has been shown recently that such a continuous time walk needs time $\Omega(N)$ to perform the same task. Our result furthermore improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of $O(\sqrt{N})$ and give several extensions of quantum walk search algorithms for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another ``natural'' choice of coin gives a walk that takes $\Omega(N)$ steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time $O(\sqrt{N} \log N)$.
5. Pseudo Memory Effects, Majorization and Entropy in Quantum Random Walks
Anthony J. Bracken, Demosthenes Ellinas, Ioannis Tsohantjis
J. Phys. A : Math. Gen. 37 (2004) L91-L97
http://arxiv.org/abs/quant-ph/0402187
A quantum random walk on the integers exhibits pseudo memory effects, in that its probability distribution after N steps is determined by reshuffling the first N distributions that arise in a classical random walk with the same initial distribution. In a classical walk, entropy increase can be regarded as a consequence of the majorization ordering of successive distributions. The Lorenz curves of successive distributions for a symmetric quantum walk reveal no majorization ordering in general. Nevertheless, entropy can increase, and computer experiments show that it does so on average. Varying the stages at which the quantum coin system is traced out leads to new quantum walks, including a symmetric walk for which majorization ordering is valid but the spreading rate exceeds that of the usual symmetric quantum walk.