1. Exact analytical results for quantum walks on star graph
Xinping Xu
J. Phys. A 42, 115205 (2009)
http://arxiv.org/abs/0903.1149
In this paper, we study coherent exciton transport of continuous-time quantum walks on star graph. Exact analytical results of the transition probabilities are obtained by means of the Gram-Schmidt orthonormalization of the eigenstates. Our results show that the coherent exciton transport displays perfect revivals and strong localization on the initial node. When the initial excitation starts at the central node, the transport on star graph is equivalent to the transport on a complete graph of the same size.
2. The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, Fran?ois Le Gall, Seiichiro Tani
Quantum Information and Computation 10, 181-188 (2010)
http://arxiv.org/abs/0903.1291
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
3. Continuous-Time Quantum Walks and Trapping
Elena Agliari, Oliver Muelken, Alexander Blumen
http://arxiv.org/abs/0903.3288
Recent findings suggest that processes such as the electronic energy transfer through the photosynthetic antenna display quantal features, aspects known from the dynamics of charge carriers along polymer backbones. Hence, in modeling energy transfer one has to leave the classical, master-equation-type formalism and advance towards an increasingly quantum-mechanical picture, while still retaining a local description of the complex network of molecules involved in the transport, say through a tight-binding approach. Interestingly, the continuous time random walk (CTRW) picture, widely employed in describing transport in random environments, can be mathematically reformulated to yield a quantum-mechanical Hamiltonian of tight-binding type; the procedure uses the mathematical analogies between time-evolution operators in statistical and in quantum mechanics: The result are continuous-time quantum walks (CTQWs). However, beyond these formal analogies, CTRWs and CTQWs display vastly different physical properties. In particular, here we focus on trapping processes on a ring and show, both analytically and numerically, that distinct configurations of traps (ranging from periodical to random) yield strongly different behaviours for the quantal mean survival probability, while classically (under ordered conditions) we always find an exponential decay at long times.
4. Efficient Circuits for Quantum Walks
Chen-Fu Chiang, Daniel Nagaj, Pawel Wocjan
Quantum Information and Computation, Vol.10, No.5&6, pp0420-0434 (2010)
http://arxiv.org/abs/0903.3465
We present an efficient general method for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk. Our approach is based on Grover and Rudolph's method for preparing coherent versions of efficiently integrable probability distributions. This method is intended for use in quantum walk algorithms with polynomial speedups, whose complexity is usually measured in terms of how many times we have to apply a step of a quantum walk, compared to the number of necessary classical Markov chain steps. We consider a finer notion of complexity including the number of elementary gates it takes to implement each step of the quantum walk with some desired accuracy. The difference in complexity for various implementation approaches is that our method scales linearly in the sparsity parameter and poly-logarithmically with the inverse of the desired precision. The best previously known general methods either scale quadratically in the sparsity parameter, or polynomially in the inverse precision. Our approach is especially relevant for implementing quantum walks corresponding to classical random walks like those used in the classical algorithms for approximating permanents and sampling from binary contingency tables. In those algorithms, the sparsity parameter grows with the problem size, while maintaining high precision is required.
5. Orthogonal polynomials induced by discrete-time quantum walks in one dimension
Masatoshi Hamada, Norio Konno, Wojciech Mlotkowski
Interdisciplinary Information Sciences, Vol.15, No.3, pp.367-375 (2009)
http://arxiv.org/abs/0903.4047
In this paper we obtain some properties of orthogonal polynomials given by a weight function which is a limit density of a rescaled discrete-time quantum walk on the line.
6. Limit theorems for discrete-time quantum walks on trees
Kota Chisaki, Masatoshi Hamada, Norio Konno, Etsuo Segawa
Interdisciplinary Information Sciences 15, 423-429 (2009)
http://arxiv.org/abs/0903.4508
We consider a discrete-time quantum walk W_t given by the Grover transformation on the Cayley tree. We reduce W_t to a quantum walk X_t on a half line with a wall at the origin. This paper presents two types of limit theorems for X_t. The first one is X_t as t\to\infty, which corresponds to a localization in the case of an initial qubit state. The second one is X_t/t as t\to\infty, whose limit density is given by the Konno density function [1-4]. The density appears in various situations of discrete-time cases. The corresponding similar limit theorem was proved in [5] for a continuous-time case on the Cayley tree.
7. Implementation of the quantum walk step operator in lateral quantum dots
K.A. van Hoogdalem, M. Blaauboer
Phys. Rev. B 80, 125309 (2009)
http://arxiv.org/abs/0903.1236
We propose a physical implementation of the step operator of the discrete quantum walk for an electron in a one-dimensional chain of quantum dots. The operating principle of the step operator is based on locally enhanced Zeeman splitting and the role of the quantum coin is played by the spin of the electron. We calculate the probability of successful transfer of the electron in the presence of decoherence due to quantum charge fluctuations, modeled as a bosonic bath. We then analyze two mechanisms for creating locally enhanced Zeeman splitting based on, respectively, locally applied electric and magnetic fields and slanting magnetic fields. Our results imply that a success probability of > 90% is feasible under realistic experimental conditions.