Universal computation by quantum walk

TitleUniversal computation by quantum walk
Publication TypeJournal Article
Year of Publication2009
AuthorsChilds, AM
JournalPhysical Review Letters
Date Published2009/5/4

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.

Short TitlePhys. Rev. Lett.