Finding All Solutions with Grover’s Algorithm by Integrating Estimation and Discovery

Sihyung Lee, Seung Yeob Nam

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number4830
JournalElectronics (Switzerland)
Volume13
Issue number23
DOIs
StatePublished - Dec 2024

Keywords

  • Grover’s algorithm
  • quantum algorithm
  • quantum computing
  • quantum counting
  • search algorithm

Fingerprint

Dive into the research topics of 'Finding All Solutions with Grover’s Algorithm by Integrating Estimation and Discovery'. Together they form a unique fingerprint.

Cite this