1. Relativistic quantum walks
Frederick W. Strauch
Phys. Rev. A 73, 054302 (2006)
http://arxiv.org/abs/quant-ph/0508096
By pursuing the deep relation between the one-dimensional Dirac equation and quantum walks, the physical role of quantum interference in the latter is explained. It is shown that the time evolution of the probability density of a quantum walker, initially localized on a lattice, is directly analogous to relativistic wave-packet spreading. Analytic wave-packet solutions reveal a striking connection between the discrete and continuous time quantum walks.
2. A new quantum lower bound method, with an application to strong direct product theorem for quantum search
Andris Ambainis
http://arxiv.org/abs/quant-ph/0508200
We present a new method for proving lower bounds on quantum query algorithms. The new method is an extension of adversary method, by analyzing the eigenspace structure of the problem. Using the new method, we prove a strong direct product theorem for quantum search. This result was previously proven by Klauck, Spalek and de Wolf (quant-ph/0402123) using polynomials method. No proof using adversary method was known before.
3. Quantum Algorithms for Matching and Network Flows
Andris Ambainis, Robert Spalek
http://arxiv.org/abs/quant-ph/0508205
We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time O(n^2 (sqrt{m/n} + log n) log n), and finding a maximal flow in an integer network in time O(min(n^{7/6} sqrt m * U^{1/3}, sqrt{n U} m) log n), where n is the number of vertices, m is the number of edges, and U <= n^{1/4} is an upper bound on the capacity of an edge.