Phys. Rev. A 70, 042312 (2004) [5 pages]Spatial search and the Dirac equationReceived 1 June 2004; published 19 October 2004 We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order √N for d>2 and of order √N log N in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), 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. © 2004 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevA.70.042312
DOI:
10.1103/PhysRevA.70.042312
PACS:
03.67.Lx
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.