Zhu Yuanye, Wang Zeguo, Yan Bao, Wei Shijie
State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China.
State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China.
Entropy (Basel). 2021 Dec 8;23(12):1649. doi: 10.3390/e23121649.
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 λ=M/N, where is the number of marked state and 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 ON 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±MN, our algorithm will find the target states with a success rate no less than 96%.
量子搜索算法是量子算法的里程碑之一。与经典算法相比，在对未排序数据库中的标记状态进行搜索时，它具有二次加速特性。然而，量子搜索算法的成功率对标记状态的数量很敏感。在本文中，我们研究了在给定λ = M/N的量子搜索算法中成功率与迭代次数之间的关系，其中M是标记状态的数量，N是数据集中项目的数量。我们基于格罗弗 - 朗算法开发了一种在标记状态数量存在一定不确定性时的鲁棒量子搜索算法。所提出的算法与格罗弗算法具有相同的查询复杂度O(√N)，并且对M/N比值的不确定性具有高容忍度。特别是，对于比值在M±√MN范围内存在不确定性的数据库，我们的算法将以不低于96%的成功率找到目标状态。
