1. Driving quantum walk spreading with the coin operator
Alejandro Romanelli
http://arxiv.org/abs/0908.0019
We generalize the discrete quantum walk on the line using a time dependent unitary coin operator. We find an analytical relation between the long-time behaviors of the standard deviation and the coin operator. Selecting the coin time sequence allows to obtain a variety of predetermined asymptotic wave-function spreadings: ballistic, sub-ballistic, diffusive, sub-diffusive and localized.
2. Quantum random walks on the $N$-cycle subject to decoherence on the coin degree of freedom
Chaobin Liu, Nelson Petulante
Phys. Rev. E 81, 031113 (2010)
http://arxiv.org/abs/0908.1524
For a discrete time quantum walk (QW) on the $N$-cycle, allowing for decoherence on the coin, we derive a number of new results, including an explicit formula for the position probability distribution. For a QW of this type, we show that the mixing behavior tends, in the long-run, to a uniform distribution, regardless of the initial state of the system and irrespective of the parity of the number of nodes $N$. These results confirm the findings of previous authors who arrived at similar conclusions through extensive numerical simulations. In particular, we infer that the mixing time $\bar{M(\epsilon)}$ for the time-everaged probability distribution is of order no greater than $O(N^2/\epsilon)$.
3. Localization of an inhomogeneous discrete-time quantum walk on the line
Norio Konno
Quantum Information Processing, Vol.9, No.3, pp.405-418 (2010)
http://arxiv.org/abs/0908.2213
We investigate a space-inhomogeneous discrete-time quantum walk in one dimension. We show that the walk exhibits localization by a path counting method.
4. Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
http://arxiv.org/abs/0908.2468
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).
5. Limitations on the simulation of non-sparse Hamiltonians
Andrew M. Childs, Robin Kothari
Quantum Information and Computation 10, 669-684 (2010)
http://arxiv.org/abs/0908.4398
The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(||Ht||poly(log N)) operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.
6. Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory
S. Salimi
Quantum Inf. Process 9 (2010) 75.
http://arxiv.org/abs/0908.4546
We analyze continuous-time quantum and classical random walk on spidernet lattices. In the framework of Stieltjes transform, we obtain density of states, which is an efficiency measure for the performance of classical and quantum mechanical transport processes on graphs, and calculate the spacetime transition probabilities between two vertices of the lattice. Then we analytically show that there are two power law decays $\sim t^{-3}$ and $\sim t^{-1.5}$ at the beginning of the transport for transition probability in the continuous-time quantum and classical random walk respectively. This results illustrate the decay of quantum mechanical transport processes is quicker than that of the classical one. Due to the result, the characteristic time $t_c$, which is the time when the first maximum of the probabilities occur on an infinite graph, for the quantum walk is shorter than that of the classical walk. Therefore, we can interpret that the quantum transport speed on spidernet is faster than that of the classical one. In the end, we investigate the results by numerical analysis for two examples.