Abstract
In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.
- Received 11 June 2008
DOI:https://doi.org/10.1103/PhysRevLett.102.180501
©2009 American Physical Society