Send to

Choose Destination
Phys Rev Lett. 2009 May 8;102(18):180501. Epub 2009 May 4.

Universal computation by quantum walk.

Author information

Department of Combinatorics and Institute for Quantum Computing, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1.


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.

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center