01608nas a2200157 4500008004100000245005700041210005600098260001500154300001400169490000800183520116700191100002301358700001801381700001401399856003701413 2013 eng d00aUniversal computation by multi-particle quantum walk0 aUniversal computation by multiparticle quantum walk c2013/02/14 a791 - 7940 v3393 a A quantum walk is a time-homogeneous quantum-mechanical process on a graph
defined by analogy to classical random walk. The quantum walker is a particle
that moves from a given vertex to adjacent vertices in quantum superposition.
Here we consider a generalization of quantum walk to systems with more than one
walker. 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. Multi-particle
quantum walk includes a broad class of interacting many-body systems such as
the Bose-Hubbard model and systems of fermions or distinguishable particles
with nearest-neighbor interactions. We show that multi-particle quantum walk is
capable of universal quantum computation. Since it is also possible to
efficiently simulate a multi-particle quantum walk of the type we consider
using a universal quantum computer, this model exactly captures the power of
quantum computation. In principle our construction could be used as an
architecture for building a scalable quantum computer with no need for
time-dependent control.
1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1205.3782v2