https://doi.org/10.1140/epjqt/s40507-023-00204-y
Research
Determination of the number of shots for Grover’s search algorithm
1
Department of Applied Mathematics and Statistics, Universidad Politécnica de Cartagena, Cartagena, Spain
2
Department of Information Technologies and Communications, Universidad Politécnica de Cartagena, Plaza del Hospital, 1, 30202, Cartagena, Spain
Received:
21
November
2022
Accepted:
27
October
2023
Published online:
8
November
2023
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.
Key words: Grover’s algorithm / Shots / Search problem / Quantum computing
© The Author(s) 2023
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
