Multi-Solution Search and Solution-Count Estimation with Grover’s Algorithm: A Survey

Abstract

Grover’s algorithm delivers a quadratic speed-up for searching an unstructured space, but its behaviour is governed by a single, easily mis-set quantity: the number of marked items M. A single search must apply the Grover iterator close to ⌊π/4 × √(N/M)⌋ times, and any deviation drives the success probability away from its peak. The problem becomes acute when the goal is not one solution but the complete set of solutions, because each measurement returns at most one item and an inaccurate count causes searches to stop early, repeat needlessly, or run without end. This survey organises the literature around two tightly coupled questions: how to enumerate many or all solutions efficiently, and how to obtain and maintain a usable estimate of the solution count. We review the geometry of amplitude amplification and the overshoot phenomenon, the principal families of find-all strategies (sampling with replacement, oracle modification, and over-sampling), the spectrum of counting and amplitude-estimation techniques (phase-estimation-based counting, maximum-likelihood and iterative estimators, and signal-processing formulations), and the count-free approaches based on exponential schedules and fixed-point amplification. We compare query and space costs, analyse the cost–accuracy trade-off that links estimation to discovery, and discuss the recent move toward adaptive, quantum–classical hybrid schemes that refine the count during execution. We close with open problems on near-term hardware, robustness, and the interaction between algorithmic and physical error.

Keywords: Quantum search, grover’s algorithm, amplitude amplification, quantum counting, amplitude estimation, multi-solution enumeration, fixed-point search, quantum–classical hybrid algorithms.