Robust Quantum Search with Uncertain Number of Target States

The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given [Formula: see text] , where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity [Formula: see text] as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio [Formula: see text]. In particular, for a database with an uncertainty in the ratio [Formula: see text] , our algorithm will find the target states with a success rate no less than [Formula: see text].