%0 Journal Article
%J Physical Review Letters
%D 2009
%T Universal computation by quantum walk
%A Andrew M. Childs
%X In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.
%B Physical Review Letters
%V 102
%8 2009/5/4
%G eng
%U http://arxiv.org/abs/0806.1972v1
%N 18
%! Phys. Rev. Lett.
%R 10.1103/PhysRevLett.102.180501