4.5 Article

Determination of the number of shots for Grover's search algorithm

期刊

EPJ QUANTUM TECHNOLOGY
卷 10, 期 1, 页码 -

出版社

SPRINGER
DOI: 10.1140/epjqt/s40507-023-00204-y

关键词

Grover's algorithm; Shots; Search problem; Quantum computing

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

This paper studies the distribution of the required number of shots to find solutions in Grover's quantum search algorithm. It presents formulas to compute the number of shots needed and derives a probability mass function to assess the validity of the asymptotic approximations. A rule of thumb is proposed for choosing between the two approaches.
This paper focuses on Grover's quantum search algorithm, which is of paramount importance as a masterpiece of Quantum Computing software. Given the inherent probabilistic nature of quantum computers, quantum programs based on Grover's algorithm need to be run a number of times in order to generate a histogram of candidate values for solutions, which are then checked to identify the valid ones. In this paper, the distribution of the required number of shots to find all or a fraction of all the solutions to the Grover's search problem is studied. Firstly, considering the similarity of the probability problem with the well-known coupon collector's problem, two formulae are obtained from asymptotic results on the distribution of the required number of shots, as the number of problem solutions grows. These expressions allow to compute the number of shots required to ensure that, with probability p, all or a fraction of all the solutions are found. Secondly, the probability mass function of the required number of shots is derived, which serves as a benchmark to assess the validity of the asymptotic approximations derived previously. A comparison between the two approaches is presented and, as a result, a rule of thumb to decide under which circumstances employ one or the other is proposed.

作者

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

评论

主要评分

4.5
评分不足

次要评分

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

推荐

暂无数据
暂无数据