1. Equivalence between discrete quantum walk models in arbitrary topologies
F. M. Andrade, M. G. E. da Luz
Phys. Rev. A 80, 052301 (2009)
http://arxiv.org/abs/0911.0042
Coin and scattering are the two major formulations for discrete quantum walks models, each believed to have its own advantages in different applications. Although they are related in some cases, it was an open question their equivalence in arbitrary topologies. Here we present a general construction for the two models for any graph and also for position dependent transition amplitudes. We then prove constructively their unitary equivalence. Defining appropriate projector operators, we moreover show how to obtain the probabilities for one model from the evolution of the other.
2. The Need for Structure in Quantum Speedups
Scott Aaronson, Andris Ambainis
http://arxiv.org/abs/0911.0996
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle.
3. Searching via walking: How to find a marked subgraph of a graph using quantum walks
Mark Hillery, Daniel Reitzner, Vladimir Buzek
http://arxiv.org/abs/0911.1102
We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has N vertices and the subgraph has K vertices, the particle becomes localized on the subgraph in O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resource needed for a quantitative comparison of the efficiency of classical and quantum searches -- the number of oracle calls.
4. One Dimensional Quantum Walks with Memory
Michael McGettrick
Quantum Information and Computation, Vol. 10, No. 5&6 (2010) 0509-0524
http://arxiv.org/abs/0911.1653
We investigate the quantum versions of a one-dimensional random walk, whose corresponding Markov Chain is of order 2. This corresponds to the walk having a memory of up to two previous steps. We derive the amplitudes and probabilities for these walks, and point out how they differ from both classical random walks, and quantum walks without memory.
5. A Quantum Lovasz Local Lemma
Andris Ambainis, Julia Kempe, Or Sattath
Journal of the ACM, Volume 59 Issue 5, October 2012, Article No. 24
http://arxiv.org/abs/0911.1696
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e \cdot k)$ of them, has a joint satisfiable state. We then apply our results to the recently studied model of random k-QSAT. Recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. we greatly extend the known satisfiable region for random k-QSAT to a density of $\Omega(2^k/k^2)$. Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.
6. Realization of a quantum walk with one and two trapped ions
F. Z?hringer, G. Kirchmair, R. Gerritsma, E. Solano, R. Blatt, C. F. Roos
Phys. Rev. Lett. 104, 100503 (2010)
http://arxiv.org/abs/0911.1876
We experimentally demonstrate a quantum walk on a line in phase space using one and two trapped ion. A walk with up to 23 steps is realized by subjecting an ion to state-dependent displacement operations interleaved with quantum coin tossing operations. To analyze the ion's motional state after each step we apply a technique that directly maps the probability density distribution onto the ion's internal state. The measured probability distributions and the position's second moment clearly show the non-classical character of the quantum walk. To further highlight the difference between the classical (random) and the quantum walk, we demonstrate the reversibility of the latter. Finally, we extend the quantum walk by using two ions, giving the walker the additional possibility to stay instead of taking a step.
7. The effect of decoherence on mixing time in continuous-time quantum walks on one-dimension regular networks
S. Salimi, R. Radgohar
International Journal of Quantum Information, Vol. 8, No. 5 (2010) 795-806
http://arxiv.org/abs/0911.4898
In this paper, we study decoherence in continuous-time quantum walks (CTQWs) on one-dimension regular networks. For this purpose, we assume that every node is represented by a quantum dot continuously monitored by an individual point contact(Gurvitz's model). This measuring process induces decoherence. We focus on small rates of decoherence and then obtain the mixing time bound of the CTQWs on one-dimension regular network which its distance parameter is $l\geq 2$. Our results show that the mixing time is inversely proportional to rate of decoherence which is in agreement with the mentioned results for cycles in \cite{FST,VKR}. Also, the same result is provided in \cite{SSRR} for long-range interacting cycles. Moreover, we find that this quantity is independent of distance parameter $l(l\geq 2)$ and that the small values of decoherence make short the mixing time on these networks.