1. One-dimensional discrete-time quantum walks on random environments
Norio Konno
Quantum Information Processing, Vol.8, No.5, pp.387-399 (2009)
http://arxiv.org/abs/0904.0392
We consider discrete-time nearest-neighbor quantum walks on random environments in one dimension. Using the method based on a path counting, we present both quenched and annealed weak limit theorems for the quantum walk.
2. Quantum walk on a line for a trapped ion
Peng Xue, Barry C. Sanders, Dietrich Leibfried
Phys. Rev. Lett. 103, 183602 (2009)
http://arxiv.org/abs/0904.1451
We show that a multi-step quantum walk can be realized for a single trapped ion with interpolation between quantum and random walk achieved by randomizing the generalized Hadamard coin flip phase. The signature of the quantum walk is manifested not only in the ion's position but also its phonon number, which makes an ion trap implementation of the quantum walk feasible.
3. Fast Amplification of QMA
Daniel Nagaj, Pawel Wocjan, Yong Zhang
QIC Vol.9 No.11&12 (2009), 1053-1068
http://arxiv.org/abs/0904.1549
Given a verifier circuit for a problem in QMA, we show how to exponentially amplify the gap between its acceptance probabilities in the `yes' and `no' cases, with a method that is quadratically faster than the procedure given by Marriott and Watrous. Our construction is natively quantum, based on the analogy of a product of two reflections and a quantum walk. Second, in some special cases we show how to amplify the acceptance probability for good witnesses to 1, making a step towards the proof that QMA with one-sided error is equal to QMA. Finally, we simplify the filter-state method to search for QMA witnesses by Poulin and Wocjan.
4. Mixing and Decoherence in Continuous-time quantum walks on long-range interacting cycles
S. Salimi, R. Radgohar
J. Phys. A: Math. Theor. 42 (2009) 475302
http://arxiv.org/abs/0904.1952
We study the effect of small decoherence in continuous-time quantum walks on long-range interacting cycles, which are constructed by connecting all the two nodes of distance m on the cycle graph. In our investigation, each node is continuously monitored by an individual point contact, which induces the decoherence process. We obtain the analytical probability distribution and the mixing time upper bound. Our results show that, for small rates of decoherence, themixing time upper bound is independent of distance parameter m and is proportional to inverse of decoherence rate.
5. Continuous-time quantum walks on star graphs
S. Salimi
Annals of Physics 324 (2009) 1185–1193
http://arxiv.org/abs/0904.2054
In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for $N$-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on $K_2$ graphs (Complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.
6. Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs
S. Salimi, M. A. Jafarizadeh
Commun. Theor. Phys. 51 (2009) 1003-1009
http://arxiv.org/abs/0904.2057
In this paper we define direct product of graphs and give a recipe for obtained probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph obtain by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determine probability of walk on complicated graphs. Using this method, we calculate the probability of continuous-time classical and quantum random walks on many of finite direct product cayley graphs (complete cycle, complete $K_n$, charter and $n$-cube). Also, we inquire that the classical state the stationary uniform distribution is reached as $t\longrightarrow \infty$ but for quantum state is not always satisfy.
7. Efficient quantum circuits for arbitrary sparse unitaries
Stephen P. Jordan, Pawel Wocjan
Phys. Rev. A 80, 062301 (2009)
http://arxiv.org/abs/0904.2211
Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms.
8. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
Ben W. Reichardt
Extended abstract in Proc. 50th IEEE Symp. on Foundations of Computer Science (FOCS), 2009, pages 544-551
http://arxiv.org/abs/0904.2759
The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal "witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a quantum algorithm for evaluating span programs with only a logarithmic query overhead on the witness size. The first result is motivated by a quantum algorithm for evaluating composed span programs. The algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal quantum algorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result extends span programs' applicability beyond the formula evaluation problem. A strong universality result for span programs follows. A good quantum query algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs are a promising model for developing more quantum algorithms.
9. Pseudo-Hermitian continuous-time quantum walks
S. Salimi, A. Sorouri
J. Phys. A: Math. Theor. 43 (2010) 275304
http://arxiv.org/abs/0904.4026
In this paper we present a model exhibiting a new type of continuous-time quantum walk (as a quantum mechanical transport process) on networks, which is described by a non-Hermitian Hamiltonian possessing a real spectrum. We call it pseudo-Hermitian continuous-time quantum walk. We introduce a method to obtain the probability distribution of walk on any vertex and then study a specific system. We observe that the probability distribution on certain vertices increases compared to that of the Hermitian case. This formalism makes the transport process faster and can be useful for search algorithms.
10. Quantum walk of a trapped ion in phase space
H. Schmitz, R. Matjeschk, Ch. Schneider, J. Glueckert, M. Enderlein, T. Huber, T. Schaetz
http://arxiv.org/abs/0904.4214
We implement the proof of principle for the quantum walk of one ion in a linear ion trap. With a single-step fidelity exceeding 0.99, we perform three steps of an asymmetric walk on the line. We clearly reveal the differences to its classical counterpart if we allow the walker/ion to take all classical paths simultaneously. Quantum interferences enforce asymmetric, non-classical distributions in the highly entangled degrees of freedom (of coin and position states). We theoretically study and experimentally observe the limitation in the number of steps of our approach, that is imposed by motional squeezing. We propose an altered protocol based on methods of impulsive steps to overcome these restrictions, in principal allowing to scale the quantum walk to several hundreds of steps.
11. Quantum walk on the line with quantum rings
Orsolya K��lm��n, Tam��s Kiss, P��ter F?ldi
Phys. Rev. B 80, 035327 (2009)
http://arxiv.org/abs/0904.4588
We propose a scheme to implement the one-dimensional coined quantum walk with electrons transported through a two-dimensional network of spintronic semiconductor quantum rings. The coin degree of freedom is represented by the spin of the electron, while the discrete position of the walker corresponds to the label of the rings in one of the spatial directions in the network. We assume that Rashba-type spin-orbit interaction is present in the rings, the strength of which can be tuned by an external electric field. The geometry of the device, together with the appropriate spin-orbit interaction strengths, ensure the realization of the coin-toss (i.e. spin-flip) and the step operator.