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 ? = v M/N, 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 O( v N) as the Grover's algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M & PLUSMN; v M/N, our algorithm will find the target states with a success rate no less than 96%.

Automated summary

The quantum search algorithm is a milestone in quantum algorithms, showing quadratic speed-up compared to classical algorithms when searching marked states in an unsorted database, but sensitivity to the number of marked states. This paper studies the relationship between success rate and number of iterations, proposing a robust quantum search algorithm with uncertainty in the number of marked states, maintaining the same query complexity as Grover's algorithm and high tolerance for uncertainty. Specifically, for databases with uncertainty in the M/N ratio, the algorithm achieves a success rate of no less than 96% in finding target states.