1. Quantum algorithms for search with wildcards and combinatorial group testing
Andris Ambainis, Ashley Montanaro
Quantum Information & Computation, vol. 14 no. 5&6, pp. 439-453, 2014
http://arxiv.org/abs/1210.1148
We consider two combinatorial problems. The first we call "search with wildcards": given an unknown n-bit string x, and the ability to check whether any subset of the bits of x is equal to a provided query string, the goal is to output x. We give a nearly optimal O(sqrt(n) log n) quantum query algorithm for search with wildcards, beating the classical lower bound of Omega(n) queries. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem. The second problem we consider is combinatorial group testing, which is the task of identifying a subset of at most k special items out of a set of n items, given the ability to make queries of the form "does the set S contain any special items?" for any subset S of the n items. We give a simple quantum algorithm which uses O(k log k) queries to solve this problem, as compared with the classical lower bound of Omega(k log(n/k)) queries.
2. Nested Quantum Walks with Quantum Data Structures
Stacey Jeffery, Robin Kothari, Frederic Magniez
http://arxiv.org/abs/1210.1199
We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the $O(n^{35/27})$ and $O(n^{9/7})$ learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.
3. Fractional Quantum Field Theory, Path Integral, and Stochastic Differential Equation for Strongly Interacting Many-Particle Systems
H. Kleinert
EPL, 100 (2012) 10001
http://arxiv.org/abs/1210.2630
While free and weakly interacting particles are well described by a a second-quantized nonlinear Schr\"odinger field, or relativistic versions of it, the fields of strongly interacting particles are governed by effective actions, whose quadratic terms are extremized by fractional wave equations. Their particle orbits perform universal L\'evy walks rather than Gaussian random walks with perturbations.
4. Quantum random walk in periodic potential on a line
Min Li, Yong-Sheng Zhang, Guang-Can Guo
http://arxiv.org/abs/1210.3112
We investigated the discrete-time quantum random walks on a line in periodic potential. The probability distribution with periodic potential is more complex compared to the normal quantum walks, and the standard deviation $\sigma$ has interesting behaviors for different period $q$ and parameter $\theta$. We studied the behavior of standard deviation with variation in walk steps, period, and $\theta$. The standard deviation increases approximately linearly with $\theta$ and decreases with $1/q$ for $\theta\in(0,\pi/4)$, and increases approximately linearly with $1/q$ for $\theta\in[\pi/4,\pi/2)$. When $q=2$, the standard deviation is lazy for $\theta\in[\pi/4+n\pi,3\pi/4+n\pi],n\in Z$.
5. Average position in quantum walks with a U(2) coin
Min Li, YOng-Sheng Zhang, Guang-Can Guo
http://arxiv.org/abs/1210.3118
We investigated discrete-time quantum walks with an arbitary unitary coin. Here we discover that the average position $
=\max( \sin(\alpha+\gamma)$, while the initial state is $1/\sqrt{2}(\mid0L>+i\mid0R>)$. We prove the result and get some symmetry properties of quantum walks with a U(2) coin with $\mid0L>$ and $\mid0R>$ as the initial state. </p> </blockquote> ------ **6. Braiding Interactions in Anyonic Quantum Walks** Lauri J. Lehman, Vaclav Zatloukal, Jiannis K. Pachos, Gavin K. Brennen Quantum Computers and Computing, 2012, 12 (1), pp. 51-62 http://arxiv.org/abs/1210.3446 ------ **7. Resonant quantum kicked rotor with two internal levels** Guzm��n Hern��ndez, Alejandro Romanelli http://arxiv.org/abs/1210.7256The anyonic quantum walk is a dynamical model describing a single anyon propagating along a chain of stationary anyons and interacting via mutual braiding statistics. We review the recent results on the effects of braiding statistics in anyonic quantum walks in quasi-one dimensional ladder geometries. For anyons which correspond to spin-1/2 irreps of the quantum groups $SU(2)_k$, the non-Abelian species $(1<k<\infty)$ gives rise to entanglement between the walker and topological degrees of freedom which is quantified by quantum link invariants over the trajectories of the walk. The decoherence is strong enough to reduce the walk on the infinite ladder to classical like behaviour. We also present numerical results on mixing times of $SU(2)_2$ or Ising model anyon walks on cyclic graphs. Finally, the possible experimental simulation of the anyonic quantum walk in Fractional Quantum Hall systems is discussed.
------ **8. Quantum transport with coupled cavities on the Apollonian network** Guilherme M. A. Almeida, Andr�� M. C. Souza Physical Review A 87, 033804 (2013) http://arxiv.org/abs/1210.8450We develop a system consisting of a quantum kicked rotor with an additional degree of freedom. This models a single two-level atom with internal ground and excited states, and it is characterized by its quantum resonances with ballistic spreading and by the entanglement between the internal and momentum degrees of freedom. These behaviors establish an equivalence between our model and the usual quantum walk on the line.
------ **9. Transport of Entanglement** Manabu Machida, Vadim A Markel, John C Schotland http://arxiv.org/abs/1210.4952We study the dynamics of single photonic and atomic excitations in the Jaynes-Cummings-Hubbard (JCH) model where the cavities are arranged in an Apollonian network (AN). The existence of a gapped field normal frequency spectrum along with strongly localized eigenstates on the AN highlights many of the features provided by the model. By numerically diagonalizing the JCH Hamiltonian in the single excitation subspace, we evaluate the time evolution of fully localized initial states, for many energy regimes. We provide a detailed description of the photonic quantum walk on the AN and also address how an effective Jaynes-Cummings interaction can be achieved at the strong hopping regime. When the hopping rate and the atom-field coupling strength is of the same order, the excitation is relatively allowed to roam between atomic and photonic degrees of freedom as it propagates. However, different cavities will contribute mostly to one of these components, depending on the detuning and initial conditions, in contrast to the strong atom-field coupling regime, where atomic and photonic modes propagate identically.
------We consider the propagation of two-photon light in a random medium. We show that the Wigner distribution of the two-photon wave function obeys an equation that is analogous to the radiative transport equation for classical light. Using this result, we predict that the entanglement of a photon pair is destroyed with propagation.