The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of [Formula: see text] marked locations for which the number of steps of the algorithm differs by a factor of [Formula: see text]. Second, we present two configurations of [Formula: see text] and [Formula: see text] marked locations having the same number of steps and probability of finding a marked location.
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of [Formula: see text] marked locations for which the number of steps of the algorithm differs by a factor of [Formula: see text]. Second, we present two configurations of [Formula: see text] and [Formula: see text] marked locations having the same number of steps and probability of finding a marked location.
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of k marked locations for which the number of steps of the algorithm differs by Ω(k) factor. Second, we present two configurations of k and k marked locations having the same number of steps and probability to find a marked location.
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.
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjacent marked vertices. The analysis is done for the two-dimensional grid and hypercube, and then is generalized for any graph. Additionally, we consider an algorithmic application of the found effect. We investigate a problem of detection of a perfect matching in a bipartite graph. We use the found effect as an algorithmic building block and construct quantum algorithm which, for a specific class of graphs, outperforms its classical analogs.
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω( N ) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjacent marked vertices. The analysis is done for the two-dimensional grid and hypercube, and then is generalized for any graph. Additionally, we consider an algorithmic application of the found effect. We investigate a problem of detection of a perfect matching in a bipartite graph. We use the found effect as an algorithmic building block and construct quantum algorithm which, for a specific class of graphs, outperforms its classical analogs.
Nature of quantum walk in presence of multiple marked state has been studied by Nahimovs and Rivosh \cite{10.1007/978-3-662-49192-8_31}. They have shown that if the marked states are arranged in a k×k cluster in a N×N grid, then to find a single marked state among the multiple ones, quantum walk requires Ω(N−k) time. In this paper, we show that using lackadaisical quantum walk with the weight of the self-loop as N(k+⌊2k⌋)4, where k is odd, the probability of finding a marked state increases by ∼0.2. Furthermore, we show that instead of applying the quantum walk O(k) times to find all the marked states, classical search in the vicinity of the marked state found after the first implementation of the quantum walk can find all the marked states in O(k) time on average.
The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.