Universal computation by quantum walk
arXiv:0806.1972 · doi:10.1103/PhysRevLett.102.180501
Abstract
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.
9 pages
References in corpus (9)
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Spatial search and the Dirac equation
- Quantum algorithms for hidden nonlinear structures
- Quantum simulators, continuous-time automata, and translationally invariant systems
- Hamiltonian Quantum Cellular Automata in 1D
- Several natural BQP-Complete problems
- The Computational Power of Symmetric Hamiltonians
- Universal quantum walks and adiabatic algorithms by 1D Hamiltonians