We show that multi-particle quantum walk is capable of universal quantum computation. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. As in a previous single-particle construction, we use a discrete version of scattering theory to establish universality. However, we use a different encoding of quantum data and exploit interactions between particles to implement two-qubit gates. In our scheme, an n-qubit circuit with g gates can be simulated by the dynamics of O(n) particles evolving for time poly(n,g) on a planar graph of maximum degree 4 with poly(n,g) vertices. Thus our graphs are exponentially smaller (as a function of n) than those used in the single-particle construction, offering the potential for efficient implementation by a system with a physical degree of freedom for each vertex of the graph. Our results apply to a broad class of multi-particle quantum walk Hamiltonians, including the Bose-Hubbard model and models with nearest-neighbor interactions for fermions and distinguishable particles.

Based on joint work with David Gosset and Zak Webb

Quantum query complexity has recently seen a lot of progress. One of the most prominent results is certainly that the generalized adversary bound characterizes the bounded-error quantum query complexity for any function. This fundamental result however does not answer all questions about quantum query complexity as it suffers from two limitations. First, the result is non constructive, and there still exist functions for which we can prove a tight lower bound using the polynomial method, the other main lower bound technique, but for which the optimal adversary matrix is unknown. Secondly, it is sometimes necessary to prove lower bounds for exponentially low success probabilities, a regime where the generalized adversary method might not be tight. A typical example is proving a direct product theorem, which essentially states that for solving k instances of a problem in parallel, one cannot do much better than solving each instance independently.

The goal of this talk will be to provide new techniques to tackle those limitations. More precisely, we will show that the multiplicative adversary method, a variation of the original adversary method, generalizes not only the generalized adversary method, but also the polynomial method, so that it essentially encompasses all known lower bound methods. Therefore, this provides a constructive approach to cast polynomial lower bounds into the adversary method framework. Moreover, since the multiplicative adversary method satisfies a strong direct product theorem and is at least as strong as the generalized adversary bound which is tight, this implies that the quantum query complexity of any function satisfies a direct product theorem.

Based on joint work with Andris Ambainis, Loïck Magnin, Martin Rötteler and Troy Lee.

[arXiv:1012.2112] [arXiv:1104.4468] [arXiv:1209.2713]