1. Implementation of one-dimensional quantum walks on spin-orbital angular momentum space of photons
Pei Zhang, Bi-Heng Liu, Rui-Feng Liu, Hong-Rong Li, Fu-Li Li, Guang-Can Guo
Phys. Rev A 81, 052322 (2010)
http://arxiv.org/abs/1002.0638
Photons can carry spin angular momentum (SAM) and orbital angular momentum (OAM), which can be used to realize a qubit system and a high-dimension system respectively. This spin-orbital system is very suitable for implementing one-dimensional discrete-time quantum random walks. We propose a simple scheme of quantum walks on the spin-orbital angular momentum space of photons, where photons walk on the infinity OAM space controlled by their SAM. By employing the recent invention of an optical device, the so-called 'q-plate', our scheme is more simple and efficient than others because there is no Mach-Zehnder interferometer in the scheme.
2. Quantum walk approach to search on fractal structures
Elena Agliari, Alexander Blumen, Oliver Muelken
Phys. Rev. A 82, 012305 (2010)
http://arxiv.org/abs/1002.1274
We study continuous-time quantum walks mimicking the quantum search based on Grover's procedure. This allows us to consider structures, that is, databases, with arbitrary topological arrangements of their entries. We show that the topological structure of the database plays a crucial role by analyzing, both analytically and numerically, the transition from the ground to the first excited state of the Hamiltonian associated with different (fractal) structures. Additionally, we use the probability of successfully finding a specific target as another indicator of the importance of the topological structure.
3. Quantum walks can find a marked element on any graph
Hari Krovi, Fr��d��ric Magniez, Maris Ozols, J��r��mie Roland
http://arxiv.org/abs/1002.2419
We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. In the case when the marked set $M$ consists of a single vertex, the number of steps of the quantum walk is quadratically smaller than the classical hitting time $HT(P,M)$ of any reversible random walk $P$ on the graph. In the case of multiple marked elements, the number of steps is given in terms of a related quantity $HT^+(\mathit{P,M})$ which we call extended hitting time. Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the random walk $P$ and the absorbing walk $P'$, whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of this interpolation. Contrary to previous approaches, our results remain valid when the random walk $P$ is not state-transitive. We also provide algorithms in the cases when only approximations or bounds on parameters $p_M$ (the probability of picking a marked vertex from the stationary distribution) and $HT^+(\mathit{P,M})$ are known.
4. Two-particle quantum walks applied to the graph isomorphism problem
John King Gamble, Mark Friesen, Dong Zhou, Robert Joynt, S. N. Coppersmith
Phys. Rev. A 81, 052313 (2010)
http://arxiv.org/abs/1002.3003
We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRG's). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of non-isomorphic SRG's and show that interacting particles can distinguish non-isomorphic graphs that noninteracting particles cannot. We obtain the following specific results: (1) We prove that quantum walks of two noninteracting particles, Fermions or Bosons, cannot distinguish certain pairs of non-isomorphic SRG's. (2) We demonstrate numerically that two interacting Bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all non-isomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of non-isomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.
5. Discrete single-photon quantum walks with tunable decoherence
M. A. Broome, A. Fedrizzi, B. P. Lanyon, I. Kassal, A. Aspuru-Guzik, A. G. White
Physical Review Letters 104, 153602 (2010)
http://arxiv.org/abs/1002.4923
Quantum walks have a host of applications, ranging from quantum computing to the simulation of biological systems. We present an intrinsically stable, deterministic implementation of discrete quantum walks with single photons in space. The number of optical elements required scales linearly with the number of steps. We measure walks with up to 6 steps and explore the quantum-to-classical transition by introducing tunable decoherence. Finally, we also investigate the effect of absorbing boundaries and show that decoherence significantly affects the probability of absorption.