Portal de Periódicos da CAPES

Spatial search and the Dirac equation

2004; American Physical Society; Volume: 70; Issue: 4 Linguagem: Inglês

10.1103/physreva.70.042312

1538-4446

Andrew M. Childs, Jeffrey Goldstone,

Quantum Information and Cryptography

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 $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}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.