1. Faster quantum walk algorithm for the two dimensional spatial search
Avatar Tulsi
http://arxiv.org/abs/0801.0497
We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N} \times \sqrt{N}$. The previous quantum walk based algorithms take $O(\sqrt{N}\log N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present a new algorithm which solves the problem in $O(\sqrt{N\log N})$ steps, thus giving an $O(\sqrt{\log N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.
2. Quantum walks on Erdos-Renyi networks
X.-P. Xu, F. Liu
Phys. Lett. A 372, 6727 (2008)
http://arxiv.org/abs/0801.4115
We study the coherent exciton transport of continuous-time quantum walks (CTQWs) on Erdos-Renyi networks. The Erdos-Renyi network of N nodes is constructed by connecting every pair of nodes with probability $p$. We numerically calculate the ensemble averaged transition probability of quantum transport between two nodes of the networks. For finite networks, we find that the limiting transition probability is reached very quickly. For infinite networks whose spectral density follows the semicircle law, the efficiencies of the classical and quantum-mechanical transport are compared on networks of different average degree. In the long time limiting, we consider the distribution of the ensemble averaged transition probabilities, and show that there is a high probability to find the exciton at the initial node. Such high return probability almost do not alter in a wide range of connection probability p but increases rapidly when the network approaches to be fully connected. For networks whose topology is not extremely connected, the return probability is inversely proportional to the network size N. Furthermore, the transport dynamics are compared with that on a random graph model in which the degree of each node equals to the average degree of the Erdos-Renyi networks.
3. Continuous-time quantum walks on one-dimension regular networks
Xinping Xu, Feng Liu
Phys. Rev. E 77, 061127 (2008)
http://arxiv.org/abs/0801.4180
In this paper, we consider continuous-time quantum walks (CTQWs) on one-dimension ring lattice of N nodes in which every node is connected to its 2m nearest neighbors (m on either side). In the framework of the Bloch function ansatz, we calculate the spacetime transition probabilities between two nodes of the lattice. We find that the transport of CTQWs between two different nodes is faster than that of the classical continuous-time random walk (CTRWs). The transport speed, which is defined by the ratio of the shortest path length and propagating time, increases with the connectivity parameter m for both the CTQWs and CTRWs. For fixed parameter m, the transport of CTRWs gets slow with the increase of the shortest distance while the transport (speed) of CTQWs turns out to be a constant value. In the long time limit, depending on the network size N and connectivity parameter m, the limiting probability distributions of CTQWs show various paterns. When the network size N is an even number, the probability of being at the original node differs from that of being at the opposite node, which also depends on the precise value of parameter m.
4. Quantum walks: a Markovian perspective
Diego de Falco, Dario Tamascelli
V. Geffert et al. (Eds.): SOFSEM 2008, LNCS 4910, pp. 519-530, 2008
http://arxiv.org/abs/0801.4515
For a continuous-time quantum walk on a line the variance of the position observable grows quadratically in time, whereas, for its classical counterpart on the same graph, it exhibits a linear, diffusive, behaviour. A quantum walk, thus, propagates at a rate which is linear in time, as compared to the square root rate for a classical random walk. Indeed, it has been suggested that there are graphs that can be traversed by a quantum walker exponentially faster than by the classical random analogue. In this note we adopt the approach of exploring the conditions to impose on a Markov process in order to emulate its quantum counterpart: the central issue that emerges is the problem of taking into account, in the numerical generation of each sample path, the causative effect of the ensemble of trajectories to which it belongs. How to deal numerically with this problem is shown in a paradigmatic example.