1. Quantum Walk on a Line with Two Entangled Particles
Y. Omar, N. Paunkovic, L. Sheridan, S. Bose
Phys. Rev. A 74, 042304 (2006)
http://arxiv.org/abs/quant-ph/0411065
We introduce the concept of a quantum walk with two particles and study it for the case of a discrete time walk on a line. A quantum walk with more than one particle may contain entanglement, thus offering a resource unavailable in the classical scenario and which can present interesting advantages. In this work, we show how the entanglement and the relative phase between the states describing the coin degree of freedom of each particle will influence the evolution of the quantum walk. In particular, the probability to find at least one particle in a certain position after $N$ steps of the walk, as well as the average distance between the two particles, can be larger or smaller than the case of two unentangled particles, depending on the initial conditions we choose. This resource can then be tuned according to our needs, in particular to enhance a given application (algorithmic or other) based on a quantum walk. Experimental implementations are briefly discussed.
2. Quantum Walks with Entangled Coins
S.E. Venegas-Andraca, J.L. Ball, K. Burnett, S. Bose
New Journal of Physics 7 (2005) 221
http://arxiv.org/abs/quant-ph/0411151
We present a mathematical formalism for the description of unrestricted quantum walks with entangled coins and one walker. The numerical behaviour of such walks is examined when using a Bell state as the initial coin state, two different coin operators, two different shift operators, and one walker. We compare and contrast the performance of these quantum walks with that of a classical random walk consisting of one walker and two maximally correlated coins as well as quantum walks with coins sharing different degrees of entanglement. We illustrate that the behaviour of our walk with entangled coins can be very different in comparison to the usual quantum walk with a single coin. We also demonstrate that simply by changing the shift operator, we can generate widely different distributions. We also compare the behaviour of quantum walks with maximally entangled coins with that of quantum walks with non-entangled coins. Finally, we show that the use of different shift operators on 2 and 3 qubit coins leads to different position probability distributions in 1 and 2 dimensional graphs.
3. An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
http://arxiv.org/abs/quant-ph/0411152
We provide an elementary proof of the quantum adiabatic theorem.
4. Robust Quantum Algorithms for Oracle Identification
Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, Shigeru Yamashita
http://arxiv.org/abs/quant-ph/0411204
The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set $S$ of $M$ oracles and a blackbox oracle $f$. Our task is to figure out which oracle in $S$ is equal to the blackbox $f$ by making queries to $f$. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: ($i$) For any oracle set $S$ such that $|S| \le 2^{N^d}$ ($d < 1$), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$, matching the lower bound proved in \cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\log{N}}$ (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. ($iii$) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.
5. Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
Andris Ambainis, William Gasarch, Aravind Srinavasan, Andrey Utis
http://arxiv.org/abs/cs/0411076
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.