How can quantum search find all solutions when their number is unknown?

Complete search with an unknown solution count

Grover's algorithm gives a quadratic speedup for finding a marked element when the number of solutions is known, but the harder task here is different: find every element of the solution set S, when its cardinality M is unknown. The search space has N = 2^n elements, the solution fraction is λ = M/N, and because M is unknown the algorithm cannot simply run a fixed number of iterations. Instead it stops when the posterior expected number of undiscovered solutions falls to a prescribed tolerance ε.

A second complication is that measuring a candidate does not reveal whether it is a solution. Each measured candidate still needs a verification of f(x), either classically or through the quantum oracle. The paper captures this cost with the testing ratio 0 < r < 1, defined as the time of one verification divided by the time of one amplitude-amplification iteration, with r = 1 treated as the limiting case where the two costs are equal. When both classical and quantum verification are available, the faster one sets r.

Why plain Grover search is not enough

Grover's iteration combines an oracle O that flips the phase of marked states with a diffuser D. In the two-dimensional subspace spanned by the uniform superpositions of marked and unmarked states, the success probability after m iterations is P_Grover(λ, m) = sin²((2m + 1)θ), where θ = arcsin√λ. This form exposes two limitations. Choosing the iteration count that maximizes the probability requires knowing λ, and even the optimal integer count generally does not reach a success probability of one.

Generalized fixed-point quantum search, referred to in the paper as YLC search, addresses the second limitation by adding a controllable width parameter w that suppresses the overshoot. But the width is an extra parameter to tune, and the paper's question is whether that tuning ever pays for itself once the cost of each iteration is accounted for.

An adaptive Bayesian policy over three search modes

The proposed algorithm unifies classical sampling, Grover search, and YLC fixed-point search into a single adaptive Bayesian strategy. It starts from a prior over the number of solutions, updates the posterior after every instance, removes each tested element from the active search space, and then selects the next instance — and, for YLC, the width w — to maximize the posterior-predictive success probability per execution time cost. The search terminates when the posterior expected number of undiscovered solutions is at most ε.

This is a greedy, per-instance criterion, and the paper is explicit that its optimality and bound statements concern individual searching instance scores, not the total runtime of the resulting adaptive policies. That distinction matters for anyone comparing the algorithm against a fixed-iteration baseline.

Below r = 1/4 fixed-point search cannot help

The paper's central threshold is r = 1/4. For every posterior distribution and for regimes where 0 < r ≤ 1/4, the authors prove that YLC fixed-point search cannot improve the best greedy score obtained from a hybrid of classical sampling and unmodified Grover search. In that regime the optimization over the YLC width can be omitted entirely.

Numerical work supports the proof. In decision trees built for a finite database of N = 16384 and for the continuum limit N → ∞, both carried to depth 20, no posterior selected a positive width at sampled ratios r ≤ 0.30. At r = 0.35, only 1400 of 2,097,151 finite-tree posterior records selected a positive width (about 0.0668%), with a maximum of w ≈ 0.0211, while 140 continuum-tree records did so (about 0.00668%), with a maximum of w ≈ 0.0247. In the paired benchmark at r = 1/4, all 36,864 pairs had identical actions, outcomes, and posterior means, with w = 0 throughout.

Above the threshold the gain has an upper bound

For 1/4 < r ≤ 1, the paper derives an upper bound on the relative score improvement achievable by fixed-point search compared with the best Grover-based score. The bound decreases as the number of amplification iterations grows, and it also bounds the additional cost a generalized iteration can carry while an advantage remains possible.

The residual analysis checks this numerically. Across all selected depths in the finite and continuum trees, the largest residual between the numerical YLC-versus-Grover gap and the theoretical prediction was 5.3 × 10⁻¹⁵, and no state exceeded its posterior-specific bound within the numerical allowance. The residuals stayed at numerical zero at r = 0.25 and nonpositive across the sampled depths and ratios.

Where classical sampling should hand off to quantum search

Starting from a uniform prior, the paper determines the optimal transition point between classical sampling and quantum searching by approximating the probability distribution of the number of solutions with an integral. For 1/4 < r ≤ 1, the first transition from classical to quantum instances is attained by an optimized instance with one amplification iteration, and the paper gives the YLC width selected at that transition.

For r < 1/4, the number of preceding classical queries has an r⁻² leading term with an explicit r⁻¹ correction. The asymptotic comparison covers 56 transitions for s ∈ {0, 1, 2, 4} and 14 ratios over 0.001 ≤ r ≤ 0.25. At r = 0.10 the absolute relative error was between 0.62% and 2.02% across the four values of s, and at r = 0.001 it fell to between 0.0000403% and 0.000213%. All 558 directly calculated transitions for s = 0, …, 4 agreed with the predictions, with m = 1 giving the first quantum crossing.

What the paired benchmark shows about runtime

The paired complete-search benchmark used a database of size N = 4096, testing ratios r ∈ {0.25, 0.50, 0.75, 1}, true solution counts M ∈ {1, …, 32, 64, 256, 1024, 4096}, and 1024 paired trials per (M, r) with shared random streams, producing 294,912 trajectories. Runtime was measured as T = Q_q + rQ_c, so each searching instance contributes its quantum depth m and the verification cost r.

At ε = 0.10, 2114 trajectories stopped before recovering every solution, less than 0.72% of the recorded trajectories. Allowing fixed-point instances reduced mean scaled runtime in many of the tested sparse cases at larger verification ratios, but the improvement was not uniform across the solution counts considered. The authors also report that increasing the stopping tolerance can lower runtime while substantially increasing the fraction of runs that leave solutions undiscovered — a trade-off between speed and completeness that the tolerance ε controls directly.

The testing ratio decides which search mode to use

The practical priority this paper establishes is a single comparison, not a general endorsement of fixed-point search. Read the testing ratio r first: if verification is cheap relative to an amplitude-amplification iteration, specifically r ≤ 1/4, the best policy is the hybrid of classical sampling and unmodified Grover search, and the YLC width can be left at zero. Only when r exceeds 1/4 does fixed-point search become a candidate, and even then its advantage over the best Grover-based score is capped by the paper's bound, which shrinks as more amplification iterations are used.

The second decision variable is the stopping tolerance ε. Because the benchmark shows that loosening ε can cut runtime while raising the share of runs that leave solutions undiscovered, the choice of ε — not the choice of search mode — is what determines how complete the result actually is. The paper's asymptotic optimality claim for the greedy policy applies to the regime of a known number of solutions much lower than the database size, where the policy's total cost is about 12.14% lower than using an exact searching instance at every stage; that reference case should not be read as extending to the unknown-M setting, where the algorithm must infer when to stop.

Sources used in this answer