1. Mixing of Quantum Walk on Circulant Bunkbeds
P. Lo, S. Rajaram, D. Schepens, D. Sullivan, C. Tamon, J. Ward
Quantum Information and Computation, Vol. 6, No. 4&5 (2006), pages 370-381.
http://arxiv.org/abs/quant-ph/0509059
We give new observations on the mixing dynamics of a continuous-time quantum walk on circulants and their bunkbed extensions. These bunkbeds are defined through two standard graph operators: the join G + H and the Cartesian product of graphs G and H.Our results include the following: 1. The quantum walk is average uniform mixing on circulants with bounded eigenvalue multiplicity. This extends a known fact about the cycles. 2. Explicit analysis of the probability distribution of the quantum walk on the join of circulants. This explains why complete partite graphs are not average uniform mixing, using the fact the complete n-vertex graph is the join of a 1-vertex graph and the (n-1)-vertex complete graph, and that the complete m-partite graph, where each partition has size n, is the m-fold join of the empty n-vertex graph. 3. The quantum walk on the Cartesian product of a m-vertex path P and a circulant G, is average uniform mixing if G is. This highlights a difference between circulants and the hypercubes. Our proofs employ purely elementary arguments based on the spectra of the graphs.
2. Non-Unitary Quantum Walks on Hyper-Cycles
Dmitry Solenov, Leonid Fedichkin
Phys. Rev. A 73, 012308 (2006)
http://arxiv.org/abs/quant-ph/0509078
We present analytical treatment of quantum walks on multidimensional hyper-cycle graphs. We derive the analytical expression of the probability distribution for strong and weak decoherence regimes. Upper bound to mixing time is obtained.
3. Continuous time quantum walks in phase space
Oliver Muelken, Alexander Blumen
Phys. Rev. A 73, 012105 (2006)
http://arxiv.org/abs/quant-ph/0509141
We formulate continuous time quantum walks (CTQW) in a discrete quantum mechanical phase space. We define and calculate the Wigner function (WF) and its marginal distributions for CTQWs on circles of arbitrary length $N$. The WF of the CTQW shows characteristic features in phase space. Revivals of the probability distributions found for continuous and for discrete quantum carpets do manifest themselves as characteristic patterns in phase space.
4. Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
Leonid Fedichkin, Dmitry Solenov, Christino Tamon
Quantum Information and Computation, Vol. 6, No. 3 (2006), 263-276.
http://arxiv.org/abs/quant-ph/0509163
We prove analytical results showing that decoherence can be useful for mixing time in a continuous-time quantum walk on finite cycles. This complements the numerical observations by Kendon and Tregenna (Physical Review A 67 (2003), 042315) of a similar phenomenon for discrete-time quantum walks. Our analytical treatment of continuous-time quantum walks includes a continuous monitoring of all vertices that induces the decoherence process. We identify the dynamics of the probability distribution and observe how mixing times undergo the transition from quantum to classical behavior as our decoherence parameter grows from zero to infinity. Our results show that, for small rates of decoherence, the mixing time improves linearly with decoherence, whereas for large rates of decoherence, the mixing time deteriorates linearly towards the classical limit. In the middle region of decoherence rates, our numerical data confirms the existence of a unique optimal rate for which the mixing time is minimized.
5. Quantum Algorithm for Commutativity Testing of a Matrix Set
Yuki Kelly Itakura
http://arxiv.org/abs/quant-ph/0509206
Suppose we have k matrices of size n by n. We are given an oracle that knows all the entries of k matrices, that is, we can query the oracle an (i,j) entry of the l-th matrix. The goal is to test if each pair of k matrices commute with each other or not with as few queries to the oracle as possible. In order to solve this problem, we use a theorem of Mario Szegedy (quant-ph/0401053) that relates a hitting time of a classical random walk to that of a quantum walk. We also take a look at another method of quantum walk by Andris Ambainis (quant-ph/0311001). We apply both walks into triangle finding problem (quant-ph/0310134) and matrix verification problem (quant-ph/0409035) to compare the powers of the two different walks. We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem. It turns out Szegedy's algorithm can be generalized to solve similar problems. Therefore we use Szegedy's theorem to analyze the problem of matrix set commutativity. We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n). We generalize the technique used in coming up with the upper bound to solve a broader range of similar problems. This is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here, k and n.