4.6 Article

Robust Quantum Search with Uncertain Number of Target States

期刊

ENTROPY
卷 23, 期 12, 页码 -

出版社

MDPI
DOI: 10.3390/e23121649

关键词

quantum algorithm; quantum computation; quantum information

资金

  1. National Natural Science Foundation of China [11974205, 11774197, 12005015]
  2. National Key Research and Development Program of China [2017YFA0303700]
  3. Key Research and Development Program of Guangdong Province [2018B030325002]
  4. Beijing Advanced Innovation Center for Future Chip (ICFC)

向作者/读者索取更多资源

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.
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%.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.6
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据