1. An analytic solution for one-dimensional quantum walks
Ian Fuss, Lang White, Peter Sherman, Sanjeev Naguleswaran
http://arxiv.org/abs/0705.0077
The first general analytic solutions for the one-dimensional walk in position and momentum space are derived. These solutions reveal, among other things, new symmetry features of quantum walk probability densities and further insight into the behaviour of their moments. The analytic expressions for the quantum walk probability distributions provide a means of modelling quantum phenomena that is analogous to that provided by random walks in the classical domain.
2. Sub-ballistic behavior in quantum systems with L��vy noise
A. Romanelli, R. Siri, V. Micenmacher
Phys. Rev. E 76, 037202 (2007)
http://arxiv.org/abs/0705.0370
We investigate the quantum walk and the quantum kicked rotor in resonance subjected to noise with a L\'evy waiting time distribution. We find that both systems have a sub-ballistic wave function spreading as shown by a power-law tail of the standard deviation.
3. The Quantum Query Complexity of Algebraic Properties
Sebastian Doern, Thomas Thierauf
http://arxiv.org/abs/0705.1446
We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
4. Quantum transport on small-world networks: A continuous-time quantum walk approach
Oliver Muelken, Volker Pernice, Alexander Blumen
Phys. Rev. E 76, 051125 (2007)
http://arxiv.org/abs/0705.1608
We consider the quantum mechanical transport of (coherent) excitons on small-world networks (SWN). The SWN are build from a one-dimensional ring of N nodes by randomly introducing B additional bonds between them. The exciton dynamics is modeled by continuous-time quantum walks and we evaluate numerically the ensemble averaged transition probability to reach any node of the network from the initially excited one. For sufficiently large B we find that the quantum mechanical transport through the SWN is, first, very fast, given that the limiting value of the transition probability is reached very quickly; second, that the transport does not lead to equipartition, given that on average the exciton is most likely to be found at the initial node.
5. Quantum Measurement as a Final-State Interaction with a Macroscopic External System
K.-E. Eriksson
http://arxiv.org/abs/0705.1649
A small quantum scattering system (the microsystem) is studied in interaction with a large system (the macrosystem) described by unknown stochastic variables. The interaction between the two systems is diagonal for the microsystem in a certain orthonormal basis, and the interaction gives an imprint on the macrosystem. Moreover, the interaction is assumed to involve only small transfers of energy and momentum between the two systems (as compared to typical energies/momenta within the microsystem). The analysis is carried out within scattering theory. Calculated in the conventional way, the transition amplitude for the whole system factorizes. The interaction taking place within the macrosystem is assumed to depend on the stochastic variables in such a way that, on the average, no particular basis vector state of the microsystem is favoured. The density matrix is studied in a formalism which includes generation of the ingoing state and absorption of the final state. Then the dependence of the final state on the conventional scattering amplitude for the microsystem is highly non-linear. In the thermodynamic limit of the macrosystem, the density matrix of the ensemble (of microsystem plus macrosystem) develops into a final state which involves a set of macroscopically distinguishable states, each with the microsystem in one of the basis vector states and the macrosystem in an entangled state. For an element of the ensemble, i.e., for a single measurement, the result is instead a random walk, where the microsystem ends up in one of the basis vector states (reduction of the wave packet).
6. The meeting problem in the quantum random walk
M. Stefanak, T. Kiss, I. Jex, B. Mohring
J. Phys. A: Math. Gen. 39, 14965 (2006)
http://arxiv.org/abs/0705.1985
We study the motion of two non-interacting quantum particles performing a random walk on a line and analyze the probability that the two particles are detected at a particular position after a certain number of steps (meeting problem). The results are compared to the corresponding classical problem and differences are pointed out. Analytic formulas for the meeting probability and its asymptotic behavior are derived. The decay of the meeting probability for distinguishable particles is faster then in the classical case, but not quadratically faster. Entangled initial states and the bosonic or fermionic nature of the walkers are considered.
7. Recurrence and P��lya number of quantum walks
M. Stefanak, I. Jex, T. Kiss
Phys. Rev. Lett. 100, 020501 (2008)
http://arxiv.org/abs/0705.1991
We analyze the recurrence probability (P\'olya number) for d-dimensional unbiased quantum walks. A sufficient condition for a quantum walk to be recurrent is derived. As a by-product we find a simple criterion for localisation of quantum walks. In contrast to classical walks, where the P\'olya number is characteristic for the given dimension, the recurrence probability of a quantum walk depends in general on the topology of the walk, choice of the coin and the initial state. This allows to change the character of the quantum walk from recurrent to transient by altering the initial state.
8. Classical approach to the graph isomorphism problem using quantum walks
B. L. Douglas, J. B. Wang
J. Phys. A: Math. Theor. 41 (2008) 075303
http://arxiv.org/abs/0705.2531
Given the extensive application of classical random walks to classical algorithms in a variety of fields, their quantum analogue in quantum walks is expected to provide a fruitful source of quantum algorithms. So far, however, such algorithms have been scarce. In this work, we enumerate some important differences between quantum and classical walks, leading to their markedly different properties. We show that for many practical purposes, the implementation of quantum walks can be efficiently achieved using a classical computer. We then develop both classical and quantum graph isomorphism algorithms based on discrete-time quantum walks. We show that they are effective in identifying isomorphism classes of large databases of graphs, in particular groups of strongly regular graphs. We consider this approach to represent a promising candidate for an efficient solution to the graph isomorphism problem, and believe that similar methods employing quantum walks, or derivatives of these walks, may prove beneficial in constructing other algorithms for a variety of purposes.
9. Quantum algorithms for hidden nonlinear structures
Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani
Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 395-404
http://arxiv.org/abs/0705.2784
Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonabelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.
10. Survival Probabilities in Coherent Exciton Transfer with Trapping
Oliver Muelken, Alexander Blumen, Thomas Amthor, Christian Giese, Markus Reetz-Lamour, Matthias Weidemueller
Phys. Rev. Lett. 99, 090601 (2007)
http://arxiv.org/abs/0705.3700
In the quest for signatures of coherent transport we consider exciton trapping in the continuous-time quantum walk framework. The survival probability displays different decay domains, related to distinct regions of the spectrum of the Hamiltonian. For linear systems and at intermediate times the decay obeys a power-law, in contrast to the corresponding exponential decay found in incoherent continuous-time random walk situations. To differentiate between the coherent and incoherent mechanisms, we present an experimental protocol based on a frozen Rydberg gas structured by optical dipole traps.
11. Modifying quantum walks: A scattering theory approach
Edgar Feldman, Mark Hillery
http://arxiv.org/abs/0705.4612
We show how to construct discrete-time quantum walks on directed, Eulerian graphs. These graphs have tails on which the particle making the walk propagates freely, and this makes it possible to analyze the walks in terms of scattering theory. The probability of entering a graph from one tail and leaving from another can be found from the scattering matrix of the graph. We show how the scattering matrix of a graph that is an automorphic image of the original is related to the scattering matrix of the original graph, and we show how the scattering matrix of the reverse graph is related to that of the original graph. Modifications of graphs and the effects of these modifications are then considered. In particular we show how the scattering matrix of a graph is changed if we remove two tails and replace them with an edge or cut an edge and add two tails. This allows us to combine graphs, that is if we connect two graphs we can construct the scattering matrix of the combined graph from those of its parts. Finally, using these techniques, we show how two graphs can be compared by constructing a larger larger graph in which the two original graphs are in parallel, and performing a quantum walk on the larger graph. This is a kind of quantum walk interferometry.