1. Global Symmetry is Unnecessary for Fast Quantum Search
Jonatan Janmark, David A. Meyer, Thomas G. Wong
Phys. Rev. Lett. 112, 210502 (2014)
http://arxiv.org/abs/1403.2228
Grover's quantum search algorithm can be formulated as a quantum particle randomly walking on the (highly symmetric) complete graph, with one vertex marked by a nonzero potential. From an initial equal superposition, the state evolves in a two-dimensional subspace. Strongly regular graphs have a local symmetry that ensures that the state evolves in a \emph{three}-dimensional subspace, but most have no \emph{global} symmetry. Using degenerate perturbation theory, we show that quantum random walk search on known families of strongly regular graphs nevertheless achieves the full quantum speedup of $\Theta(\sqrt{N})$, disproving the intuition that fast quantum search requires global symmetry.
2. Spatial search by continuous-time quantum walks on crystal lattices
Andrew M. Childs, Yimin Ge
Phys. Rev. A 89, 052337 (2014)
http://arxiv.org/abs/1403.2676
We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behaviour near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt N)$ for $d>2$ and $O(\sqrt N \log N)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.
3. Photonic quantum walk in a single beam with twisted light
Filippo Cardano, Francesco Massa, Ebrahim Karimi, Sergei Slussarenko, Domenico Paparo, Corrado de Lisio, Fabio Sciarrino, Enrico Santamato, Lorenzo Marrucci
Science Advances 1, e1500087 (2015)
http://arxiv.org/abs/1403.4857
Inspired by the classical phenomenon of random walk, the concept of quantum walk has emerged recently as a powerful platform for the dynamical simulation of complex quantum systems, entanglement production and universal quantum computation. Such a wide perspective motivates a renewing search for efficient, scalable and stable implementations of this quantum process. Photonic approaches have hitherto mainly focused on multi-path schemes, requiring interferometric stability and a number of optical elements that scales quadratically with the number of steps. Here we report the experimental realization of a quantum walk taking place in the orbital angular momentum space of light, both for a single photon and for two simultaneous indistinguishable photons. The whole process develops in a single light beam, with no need of interferometers, and requires optical resources scaling linearly with the number of steps. Our demonstration introduces a novel versatile photonic platform for implementing quantum simulations, based on exploiting the transverse modes of a single light beam as quantum degrees of freedom.
4. Quantum walk on a circle with optomechanical systems
Jalil Khatibi Moqadam, Renato Portugal, Marcos Cesar de Oliveira
http://arxiv.org/abs/1403.5205
We propose an implementation of a quantum walk on a circle on an optomechanical system by encoding the walker on the phase space of a radiation field and the coin on a two-level state of a mechanical resonator. The dynamics of the system is obtained by applying Suzuki-Trotter decomposition. We numerically show that the system displays a typical behavior of quantum walks, namely, the probability distribution evolves ballistically and the standard deviation of the phase distribution is linearly proportional to the number of steps. We also analyze the effects of decoherence by using the phase damping channel on the coin space, showing the possibility to implement the quantum walk with present day technology.