Lackadaisical quantum walks with multiple marked vertices
arXiv:1808.00672
Abstract
The concept of lackadaisical quantum walk -- quantum walk with self loops -- was first introduced for discrete-time quantum walk on one-dimensional line. Later it was successfully applied to improve the running time of the spacial search on two-dimensional grid. In this paper we study search by lackadaisical quantum walk on the two-dimensional grid with multiple marked vertices. First, we show that the lackadaisical quantum walk, similarly to the regular (non-lackadaisical) quantum walk, has exceptional configuration, i.e. placements of marked vertices for which the walk has no speed-up over the classical exhaustive search. Next, we demonstrate that the weight of the self-loop suggested in the previous papers is not optimal for multiple marked vertices. And, last, we show how to adjust the weight of the self-loop to overcome the aforementioned problem.
References in corpus (8)
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- One-Dimensional Three-State Quantum Walk
- Grover Search with Lackadaisical Quantum Walks
- Faster Search by Lackadaisical Quantum Walk
- Limit distributions of three-state quantum walks: the role of coin eigenstates
- Quantum Search with Multiple Walk Steps per Oracle Query
- Search of clustered marked states with lackadaisical quantum walks