paper

Grover Search with Lackadaisical Quantum Walks

arXiv:1502.04567 · doi:10.1088/1751-8113/48/43/435304

Abstract

The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Ambainis, Kempe, and Rivosh (2005) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when scales less than , while the second requires that scale less than . Finally, continuous-time quantum walks differ from both of these discrete-time examples---the self-loops make no difference at all. These behaviors generalize to multiple marked vertices.

16 pages, 7 figures; additional 2-page corrigendum

References in corpus (6)

Cited by in corpus (61)