|
Friday, March 15, 2013 |
|
|
|
|
Universal computation by multi-particle quantum walk |
|
|
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. |