Abstract
We consider the problem of searching a -dimensional lattice of sites for a single marked location. We present a Hamiltonian that solves this problem in time of order for and of order in the critical dimension . This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of ), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.
- Received 1 June 2004
DOI:https://doi.org/10.1103/PhysRevA.70.042312
©2004 American Physical Society