1. Continuous-time quantum walks on the threshold network model
Yusuke Ide, Norio Konno
Mathematical Structures in Computer Science, Vol.20, pp.1079-1090 (2010)
http://arxiv.org/abs/1003.0055
It is well known that many real world networks have the power-law degree distribution (scale-free property). However there are no rigorous results for continuous-time quantum walks on such realistic graphs. In this paper, we analyze space-time behaviors of continuous-time quantum walks and random walks on the threshold network model which is a reasonable candidate model having scale-free property. We show that the quantum walker exhibits localization at the starting point, although the random walker tends to spread uniformly.
2. Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
Apoorva Patel, Md. Aminoor Rahaman
Phys. Rev. A82 (2010) 032330
http://arxiv.org/abs/1003.0065
Random walks describe diffusion processes, where movement at every time step is restricted to only the neighbouring locations. We construct a quantum random walk algorithm, based on discretisation of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, i.e. finding a marked vertex on a $d$-dimensional hypercubic lattice. The restriction on movement hardly matters for $d>2$, and scaling behaviour close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimise the proportionality constants of the scaling behaviour, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean field theory or the $d\to\infty$ limit). In particular, the scaling behaviour for $d=3$ is only about 25% higher than the optimal $d\to\infty$ value.
3. Simulating sparse Hamiltonians with star decompositions
Andrew M. Childs, Robin Kothari
Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science 6519, pp. 94-103 (2011)
http://arxiv.org/abs/1003.3683
We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts for time t, this algorithm uses (d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces.
4. Relationship Between Quantum Walk and Relativistic Quantum Mechanics
C. M. Chandrashekar, Subhashish Banerjee, R. Srikanth
Phys. Rev. A, 81, 062340 (2010)
http://arxiv.org/abs/1003.4656
Quantum walk models have been used as an algorithmic tool for quantum computation and to describe various physical processes. This paper revisits the relationship between relativistic quantum mechanics and the quantum walks. We show the similarities of the mathematical structure of the decoupled and coupled form of the discrete-time quantum walk to that of the Klein-Gordon and Dirac equations, respectively. In the latter case, the coin emerges as an analog of the spinor degree of freedom. Discrete-time quantum walk as a coupled form of the continuous-time quantum walk is also shown by transforming the decoupled form of the discrete-time quantum walk to the Schrodinger form. By showing the coin to be a means to make the walk reversible, and that the Dirac-like structure is a consequence of the coin use, our work suggests that the relativistic causal structure is a consequence of conservation of information. However, decoherence (modelled by projective measurements on position space) generates entropy that increases with time, making the walk irreversible and thereby producing an arrow of time. Lieb-Robinson bound is used to highlight the causal structure of the quantum walk to put in perspective the relativistic structure of quantum walk, maximum speed of the walk propagation and the earlier findings related to the finite spread of the walk probability distribution. We also present a two-dimensional quantum walk model on a two state system to which the study can be extended.
5. Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
Apoorva Patel, K.S. Raghunathan, Md. Aminoor Rahaman
Phys. Rev.A82:032331, 2010
http://arxiv.org/abs/1003.5564
We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretised according to the staggered lattice fermion formalism. $d=2$ is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behaviour. As a result, the construction used in our accompanying article \cite{dgt2search} provides an $O(\sqrt{N}\log N)$ algorithm, which is not optimal. The scaling behaviour can be improved to $O(\sqrt{N\log N})$ by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi \cite{tulsi}. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimise the proportionality constants of the scaling behaviour of the algorithm by numerically tuning the parameters.
6. Exploring Topological Phases With Quantum Walks
Takuya Kitagawa, Mark S. Rudner, Erez Berg, Eugene Demler
Phys. Rev. A 82, 033429 (2010)
http://arxiv.org/abs/1003.1729
The quantum walk was originally proposed as a quantum mechanical analogue of the classical random walk, and has since become a powerful tool in quantum information science. In this paper, we show that discrete time quantum walks provide a versatile platform for studying topological phases, which are currently the subject of intense theoretical and experimental investigation. In particular, we demonstrate that recent experimental realizations of quantum walks simulate a non-trivial one dimensional topological phase. With simple modifications, the quantum walk can be engineered to realize all of the topological phases which have been classified in one and two dimensions. We further discuss the existence of robust edge modes at phase boundaries, which provide experimental signatures for the non-trivial topological character of the system.
7. Discrete-time quantum walks on one-dimensional lattices
Xin-Ping Xu
Eur. Phys. J. B 77, 479-488 (2010)
http://arxiv.org/abs/1003.1822
In this paper, we study discrete-time quantum walks on one-dimensional lattices. We find that the coherent dynamics depends on the initial states and coin parameters. For infinite size of lattice, we derive an explicit expression for the return probability, which shows scaling behavior $P(0,t)\sim t^{-1}$ and does not depends on the initial states of the walk. In the long-time limit, the probability distribution shows various patterns, depending on the initial states, coin parameters and the lattice size. The average mixing time $M_{\epsilon}$ closes to the limiting probability in linear $N$ (size of the lattice) for large values of thresholds $\epsilon$. Finally, we introduce another kind of quantum walk on infinite or even-numbered size of lattices, and show that the walk is equivalent to the traditional quantum walk with symmetrical initial state and coin parameter.