TY - GEN
T1 - Lackadaisical quantum walks with multiple marked vertices
AU - Nahimovs, Nikolajs
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - The concept of lackadaisical quantum walk – quantum walk with self loops – was first introduced for discrete-time quantum walk on one-dimensional line [8]. Later it was successfully applied to improve the running time of the spacial search on two-dimensional grid [16]. 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 [16] 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.
AB - The concept of lackadaisical quantum walk – quantum walk with self loops – was first introduced for discrete-time quantum walk on one-dimensional line [8]. Later it was successfully applied to improve the running time of the spacial search on two-dimensional grid [16]. 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 [16] 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.
UR - https://www.scopus.com/pages/publications/85062373964
U2 - 10.1007/978-3-030-10801-4_29
DO - 10.1007/978-3-030-10801-4_29
M3 - Conference paper
AN - SCOPUS:85062373964
SN - 9783030108007
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 368
EP - 378
BT - SOFSEM 2019
A2 - Královič, Rastislav
A2 - Nawrocki, Jerzy
A2 - Catania, Barbara
A2 - Pighizzini, Giovanni
PB - Springer Verlag
T2 - 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Y2 - 27 January 2019 through 30 January 2019
ER -