Search algorithms based on discrete-time quantum walk (QW) can be considered as alterations of the standard QW: Use a different coin operator that distinguishes target and nontarget vertices, or, mark the target vertices first followed by the standard QW. Two most frequently used marking coins are [Formula: see text] and [Formula: see text] the negative identity operator and the negative Grover diffusion operator. We show that search algorithms corresponding to these four combinations can be reduced to two, denoted as [Formula: see text] and [Formula: see text], and they are equivalent when searching for nonadjacent multiple targets. For adjacent target vertices, numerical simulations show that the performance of the algorithm [Formula: see text] highly depends on the density of the underlying graph, and it outperforms [Formula: see text] when the density is large enough. At last, a generalized stationary state of both search algorithms on the graphs with even-numbered degree is provided.
Search algorithms based on discrete-time quantum walk (QW) can be considered as alterations of the standard QW: Use a different coin operator that distinguishes target and nontarget vertices, or, mark the target vertices first followed by the standard QW. Two most frequently used marking coins are [Formula: see text] and [Formula: see text] the negative identity operator and the negative Grover diffusion operator. We show that search algorithms corresponding to these four combinations can be reduced to two, denoted as [Formula: see text] and [Formula: see text], and they are equivalent when searching for nonadjacent multiple targets. For adjacent target vertices, numerical simulations show that the performance of the algorithm [Formula: see text] highly depends on the density of the underlying graph, and it outperforms [Formula: see text] when the density is large enough. At last, a generalized stationary state of both search algorithms on the graphs with even-numbered degree is provided.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
We contribute to fulfill the long-lasting gap in the understanding of the spatial search with multiple marked vertices. The theoretical framework is that of discrete-time quantum walks (QW), i.e., local unitary matrices that drive the evolution of a single particle on the lattice. QW based search algorithms are well understood when they have to tackle the fundamental problem of finding only one marked element in a $d\text{\ensuremath{-}}\text{dimensional}$ grid and it has been proven they provide a quadratic advantage over classical searching protocols. However, once we consider searching more than one element, the behavior of the algorithm may be affected by the spatial configuration of the marked elements and even the quantum advantage is no longer guaranteed. Here our main contribution is threefold: (i) we provide sufficient conditions for optimality for a multi-items QWSearch algorithm; (ii) we provide analytical evidence that almost, but not all spatial configurations with multiple marked elements are optimal; and (iii) we numerically show that the computational advantage with respect to the classical counterpart is not always certain and it does depend on the proportion of searched elements over the total number of grid points.
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 l self-loops, and we investigate its effects on Grover’s algorithm when formulated as search for a marked vertex on the complete graph of N 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 Shenvi, Kempe, and Whaley (2003) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when l scales less than N , while the second requires that l scale less than N 2 . 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.
When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.
Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.
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.