1. Parameterized Quantum Query Complexity of Graph Collision
Andris Ambainis, Kaspars Balodis, J��nis Iraids, Raitis Ozols, Juris Smotrovs
http://arxiv.org/abs/1305.1021
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ queries. \end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(\sqrt{n} \log^c n)$ queries.
2. Google In A Photonic Lattice
Kallol Roy, Ji Liu, Le Luo, R.Srikanth, Tapan Mishra, Bhanu Das, T. Srinivas
http://arxiv.org/abs/1305.1766
The quantum version of Google PageRank has recently been investigated by various groups and shown to be quadratically faster in time than the classical PageRank algorithm. In this paper we propose the implementation of Quantum PageRank by a stochastic quantum walk of correlated photons in a photonic waveguide lattice, where we allow the density matrix to evolve according to the Lindblad-Kossakowski master equation. This yields a stationary state, the diagonal of whose density matrix gives the page ranking.
3. Dynamically Disordered Quantum Walk as a Maximal Entanglement Generator
Rafael Vieira, Edgard P. M. Amorim, Gustavo Rigolin
Phys. Rev. Lett. 111, 180503 (2013)
http://arxiv.org/abs/1305.4191
We show that the entanglement between the internal (spin) and external (position) degrees of freedom of a qubit in a random (dynamically disordered) one-dimensional discrete time quantum random walk (QRW) achieves its maximal possible value asymptotically in the number of steps, outperforming the entanglement attained by using ordered QRW. The disorder is modeled by introducing an extra random aspect to QRW, a classical coin that randomly dictates which quantum coin drives the system's time evolution. We also show that maximal entanglement is achieved independently of the initial state of the walker, study the number of steps the system must move to be within a small fixed neighborhood of its asymptotic limit, and propose two experiments where these ideas can be tested.
4. Degree Distribution in Quantum Walks on Complex Networks
Mauro Faccin, Tomi Johnson, Jacob Biamonte, Sabre Kais, Piotr Migda?
Phys. Rev. X 3, 041007 (2013)
http://arxiv.org/abs/1305.6078
In this theoretical study, we analyze quantum walks on complex networks, which model network-based processes ranging from quantum computing to biology and even sociology. Specifically, we analytically relate the average long time probability distribution for the location of a unitary quantum walker to that of a corresponding classical walker. The distribution of the classical walker is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks including website ranking. The quantum distribution becomes exactly equal to the classical distribution when the walk has zero energy and at higher energies the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a Renyi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate.
5. Quantum walk in symmetric Cayley graph over $\Z_2^n$
Ilnur Khuziev
http://arxiv.org/abs/1305.6849
We show that the hitting time of the discrete quantum walk on a symmetric Cayley graph over $\Z_2^n $ from a vertex to its antipodal is polynomial in degree of the graph. We prove that returning time of quantum walk on a symmetric Cayley graph over $\Z_2^n $ is polynomial and the probability to hit is almost one. To prove it, we give a new estimation of Kravchuk coefficients. We give an example of a probabilistic polynomial algorithm that finds an antipodal vertex in symmetric Cayley graphs.
6. One-dimensional quantum walks via generating function and the CGMV method
Norio Konno, Etsuo Segawa
Quantum Information and Computations 14 (2014) pp.1165-1186
http://arxiv.org/abs/1305.1722
We treat a quantum walk (QW) on the line whose quantum coin at each vertex tends to be the identity as the distance goes to infinity. We obtain a limit theorem that this QW exhibits localization with not an exponential but a "power-law" decay around the origin and a "strongly" ballistic spreading called bottom localization in this paper. This limit theorem implies the weak convergence with linear scaling whose density has two delta measures at $x=0$ (the origin) and $x=1$ (the bottom) without continuous parts.
7. Microscopic observation of magnon bound states and their dynamics
Takeshi Fukuhara, Peter Schau?, Manuel Endres, Sebastian Hild, Marc Cheneau, Immanuel Bloch, Christian Gross
Nature 502, 76 (2013)
http://arxiv.org/abs/1305.6598
More than eighty years ago, H. Bethe pointed out the existence of bound states of elementary spin waves in one-dimensional quantum magnets. To date, identifying signatures of such magnon bound states has remained a subject of intense theoretical research while their detection has proved challenging for experiments. Ultracold atoms offer an ideal setting to reveal such bound states by tracking the spin dynamics after a local quantum quench with single-spin and single-site resolution. Here we report on the direct observation of two-magnon bound states using in-situ correlation measurements in a one-dimensional Heisenberg spin chain realized with ultracold bosonic atoms in an optical lattice. We observe the quantum walk of free and bound magnon states through time-resolved measurements of the two spin impurities. The increased effective mass of the compound magnon state results in slower spin dynamics as compared to single magnon excitations. In our measurements, we also determine the decay time of bound magnons, which is most likely limited by scattering on thermal fluctuations in the system. Our results open a new pathway for studying fundamental properties of quantum magnets and, more generally, properties of interacting impurities in quantum many-body systems.