Stationary States in Quantum Walk Search

Abstract

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 non-bipartite. 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.

arXiv comment10 pages, 9 figures

References in corpus (8)

• Quantum random walks - an introductory overview
• A Quantum Random Walk Search Algorithm
• Quantum algorithms: an overview
• From quantum cellular automata to quantum lattice gases
• On the absence of homogeneous scalar unitary cellular automata
• Grover Search with Lackadaisical Quantum Walks
• Quantum Search with Multiple Walk Steps per Oracle Query
• Quantum walks on two-dimensional grids with multiple marked locations

Cited by in corpus (10)

• Equivalence of Szegedy's and Coined Quantum Walks
• Exceptional Quantum Walk Search on the Cycle
• Upperbounds on the probability of finding marked connected components using quantum walks
• Generalized exceptional quantum walk search
• Quantum walk search by Grover search on coin space
• Multi-target quantum walk search on Johnson graph
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Quantum walk search for exceptional configurations
• Comment on Nahimovs et al. `On the probability of finding marked connected components using quantum walks'
• On the probability of finding marked connected components using quantum walks