TY - JOUR
T1 - Finding All Solutions with Grover’s Algorithm by Integrating Estimation and Discovery
AU - Lee, Sihyung
AU - Nam, Seung Yeob
N1 - Publisher Copyright:
© 2024 by the authors.
PY - 2024/12
Y1 - 2024/12
N2 - Grover’s algorithm leverages quantum computing to efficiently locate solutions in unstructured search spaces, outperforming classical approaches. Since Grover’s algorithm requires prior knowledge of the number of solutions (M) within a search space of size N, previous studies assume M is estimated beforehand and focus on identifying all solutions. Here, we propose a two-step process that integrates both the estimation of M and the discovery of the solutions, optimizing the interactions between the two steps. To enhance efficiency, the estimation step captures as many solutions as possible, leaving the discovery step to focus on the remaining ones. To ensure accuracy, the discovery step continues searching until the probability of finding additional solutions becomes sufficiently low. We implemented and evaluated our methods, showing that over 80% of solutions were found during the estimation phase, allowing the discovery phase to conclude earlier, while identifying over 99% of solutions on average. In theory, the process requires (Formula presented.) × log(M) Grover’s iterations in the worst case, but in practice, it typically terminates after iterations proportional to (Formula presented.). We expect that our methods will be applicable to various search problems and inspire further research on efficiently finding all solutions.
AB - Grover’s algorithm leverages quantum computing to efficiently locate solutions in unstructured search spaces, outperforming classical approaches. Since Grover’s algorithm requires prior knowledge of the number of solutions (M) within a search space of size N, previous studies assume M is estimated beforehand and focus on identifying all solutions. Here, we propose a two-step process that integrates both the estimation of M and the discovery of the solutions, optimizing the interactions between the two steps. To enhance efficiency, the estimation step captures as many solutions as possible, leaving the discovery step to focus on the remaining ones. To ensure accuracy, the discovery step continues searching until the probability of finding additional solutions becomes sufficiently low. We implemented and evaluated our methods, showing that over 80% of solutions were found during the estimation phase, allowing the discovery phase to conclude earlier, while identifying over 99% of solutions on average. In theory, the process requires (Formula presented.) × log(M) Grover’s iterations in the worst case, but in practice, it typically terminates after iterations proportional to (Formula presented.). We expect that our methods will be applicable to various search problems and inspire further research on efficiently finding all solutions.
KW - Grover’s algorithm
KW - quantum algorithm
KW - quantum computing
KW - quantum counting
KW - search algorithm
UR - http://www.scopus.com/inward/record.url?scp=85211940536&partnerID=8YFLogxK
U2 - 10.3390/electronics13234830
DO - 10.3390/electronics13234830
M3 - Article
AN - SCOPUS:85211940536
SN - 2079-9292
VL - 13
JO - Electronics (Switzerland)
JF - Electronics (Switzerland)
IS - 23
M1 - 4830
ER -