# 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.