Robust Quantum Search with Uncertain Number of Target States期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Robust Quantum Search with Uncertain Number of Target States

Authors:	Yuanye Zhu Zeguo Wang Bao Yan Shijie Wei

Affiliation:	1.State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China; (Y.Z.); (Z.W.); (B.Y.);2.State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China;3.Beijing Academy of Quantum Information Sciences, Beijing 100193, China

Abstract:	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 $λ = \sqrt{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 (\sqrt{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 $\frac{M \pm \sqrt{M}}{N}$ , our algorithm will find the target states with a success rate no less than $96 %$ .

Keywords:	quantum algorithm quantum computation quantum information

设为首页 | 免责声明 | 关于勤云 | 加入收藏