Faster Search by Lackadaisical Quantum Walk. (arXiv:1706.06939v2 [quant-ph] UPDATED)

In the typical model, a discrete-time coined quantum walk searching the 2D
grid for a marked vertex achieves a success probability of $O(1/\log N)$ in
$O(\sqrt{N \log N})$ steps, which with amplitude amplification yields an
overall runtime of $O(\sqrt{N} \log N)$. We show that making the quantum walk
lackadaisical or lazy by adding a self-loop of weight $4/N$ to each vertex
speeds up the search, causing the success probability to reach a constant near
$1$ in $O(\sqrt{N \log N})$ steps, thus yielding an $O(\sqrt{\log N})$
improvement over the typical, loopless algorithm. This improved runtime matches
the best known quantum algorithms for this search problem. Our results are
based on numerical simulations since the algorithm is not an instance of the
abstract search algorithm.

Article web page: